Skype just launch their 2.0 beta which comes build in with Video support a week ago. From their FAQ:
* Best ever call quality.
* One-to-one video conversations with anyone, anywhere in the world.
* Contact list grouping – organize your Skype contacts anyway you like by creating groups for ‘colleagues’, ‘friends’ and ‘family’,etc.
* Mood message and local time display – so your contacts know where you’re at and how you feel.
* Improved web presence through Skype buttons – display your Skype status on your blog or webpage.
I remember using Video4IM few months ago and I am pretty impressed. Skype 2.0 is promising (altho I wish they would spend more effort on their Skype-in…)