Video chat is possible in Ubuntu (Ekiga does it). But video chat with somebody running Windows MSN has, up to now, meant a reboot into Windows. In Ubuntu 9.10, video chat via MSN will be possible using Emesene 1.5. (More information at OMG! Ubuntu!)
Ubuntu 9.10 will also bring the new IM client Empathy (replacing Pidgin), which will also support MSN video chat at some point in the future. (OMG! Ubuntu again).