pidgin works very well can run your existing MSN, yahoo, google, AOL
and some other IMs on it

Empathy is already installed on that version of Ubuntu and will connect
to most IM networks. It is found by left clicking on the envelope icon
nest to the time.

I use Pidgin (GNOME) and Kopete (KDE) with ICQ, Google, Yahoo, MSN, and AIM
with no problems. They also work with lots of other networks. They have lots
of features and I can do whatever the people I chat with can in network
specific applications. The only problem is when Yahoo or Microsoft change
their protocols to foil generic applications, but that is short lived and
very seldom.

Lots of people are now using free Skype and their is a Linux Version.