aMSN aMSN is a powerful, highly configurable and feature-rich client for the WLM (formerly known as MSN) protocol with support for skins, plugins, system tray integration, webcam, tabbed chat windows, multi-accounts, offline messaging, chat history, display picture and many, many more. The configuration options are abundant via the Account->Preferences menu.
Pidgin This is the well-known IM client for the GNOME desktop environment with support for a wide variety of IM protocols, including AIM, Google Talk, ICQ, MSN or Yahoo. Piding also comes with a basic IRC client, support for multiple accounts, logging, system tray integration, themes, plugins.
Empathy This is yet another GNOME instant messaging client with support for Google Talk, MSN, IRC, Salut, AIM, Facebook, Yahoo, Gadu-Gadu, Groupwise, ICQ and QQ. You will have to install specific Telepathy Connection Manager components in order to support all protocols e.g. sudo apt-get install telepathy-haze. Empathy features popup and sound notifications, smileys, spell-checking and themes.
Kopete Kopete is the default chat client in KDE, offering support for a all the popular protocols (including IRC), tray integration, notifications, multiple accounts, tabbed chat windows, smileys, logs, video support and plugins.
Finch Included in the Pidign package, Finch is a text user interface IM client which runs in a terminal and is based on libpurple, the same library Pidgin uses. This means Finch supports all the protocols that Pidgin has support for, including Yahoo, WLM, IRC or Google Talk. A full guide to Finch is located on the TuxArena Blog, here.
Emesene Emesene is yet another powerful WLM client for GNOME with support for plugins, themes, notifications, webcam, configurable interface.
KMess KMess is a WLM client for KDE with support for notifications, message stacking, avatars, logging, chat styles, emoticons, mail integration.
Ayttm Ayttm is a graphical messaging application with support for Jabber, MSN, Yahoo, IRC and AIM. It features tabs, smileys, sound notifications, logging system.
Skype Although Skype is renowned for being one of the most popular voice calls application, it also supports instant messaging, file transfers and webcam. Skype is closed-source and the official download page offers packages for all the major distributions out there.
CenterIM This is a fork of CenterICQ, a terminal-based client for popular IM protocols. CenterIM supports ICQ, Yahoo, MSN, AIM, ICQ, Jabber, IRC, Live Journal and Gadu-Gadu. A feature which I found very useful was the possibility to enable Emacs or Vi bindings in the text editor, making it easier for persons who are used to these two IDEs to write text in a faster way.