Don't be jealous that Windows and Mac users are using video messaging. You can do that with your Ubuntu box too, given the right software!
To use video instant messaging in Ubuntu, you need to have a working webcam first. If you did not buy your webcam yet, I suggest taking a look at Linux USB website to check the supported models before you make your purchase (when on the Linux USB site, select “Working devices list" under “Other helpful links" and in the next page select “Devices" in the top left, finally on the following page select “Show" to the right of the “Video" section). If you already have a webcam, do a quick search on the Internet with the camera's make and model and make sure that it is supported under Linux. There is no way to make cameras work under Linux using Windows drivers unlike wireless cards, so if you have an unsupported webcam model, I'm afraid you will need to purchase a supported one.
When you are sure that you have your webcam working under Linux, and you have the necessary hardware -headset and speakers-, then you are ready to go.
Skype has a Linux release that works perfectly with webcams. Skype is one of the most famous audio/video messaging solutions, used by millions of people around the world, so you will have no problem using the software and the service. In fact, we have a full article dedicated to using Skype on your Linux computer here on Bright Hub, feel free to take a look!
Windows Live (Formerly MSN) Network
To connect to Windows Live network and have audio/video chat with your friends, you will have to download and install aMSN. It is a free Windows Live (MSN) Messenger clone, letting you transmit text, audio and video chat with your friends. Although it has many features (offline messaging, voice clips, custom emoticons, file transfers etc.) it also supports plug-ins and skinning. I strongly suggest you to take a look at aMSN plug-ins to enhance your aMSN program; there is even an aMSN Plus! plug-in available!
If you have friends using any program that supports SIP, XMPP or Gtalk networks, then you will want to install an all-in-one solution, which will be Gnome's Empathy. Although Empathy supports Jabber, MSN, IRC networks (plus the ones that are supported by Pidgin), audio and video support is limited to SIP, XMPP and Gtalk networks. The instant messaging programs that use SIP protocol are Nimbuzz, Kcall, Kphone and Fring to name a few. A few examples of programs that use XMPP are Digsby, Meebo, Miranda, Proteus (Mac OS X only), Joost and Google Talk.
There are a limited number of programs available for Linux video instant messaging, but they all do their jobs quite well. I personally believe that it is not a good idea to install multiple instant messaging clients for each and every protocol unless you have a good reason. Installing Skype, aMSN and/or Empathy should meet all your instant messaging needs.