You should not have a problem with connecting to MSN. All you need to do is download a generic messenger (the ones that let you connect to different networks at the same time). I personallly recoment Pidgin ( http://www.pidgin.im/ ) because you can connect to plenty of networks, I´m sure it's all you need.
Don't listen when someone tells you to open a new account (e.g. yahoo) Pidgin or some other program like it will let you connect to multiple instant messaging networks, like the following:
AIM,Bonjour, Gadu-Gadu, Google Talk, Groupwise, ICQ, IRC, MSN, MySpace IM, QQ, SILC, SIMPLE, Sametime, XMPP, Yahoo!, Zephyr and I'm sure soon the will even let you connect to facebook!! and many other social networks.
OH, BY THE WAY, Most Linux versions have Pidgin or something similar already installed in the system, you should check that first, so you don´t have to go through the hassle of installing something you already have.
I know because I use Ubuntu Linux and Pidgin is already there. You're welcome.