I think the Skype Beta does both audio and video. You could also use some sort of VoIP system. I've have video chats using Ekiga, although I seem to remember it being a pain to get the connection working through my router.
I have no clue about MSN... Why not ask Microsoft to release a Linux client for it? I don't expect you'll get very far, but you never know.