or you can try some Multi-Protocol IM Client, like fire (u can d/l at http://fire.sourceforge.net/)
or Adium (http://www.adiumx.com/)
I once has the same problem as yours (can't connect to MSN thru the MAC version of Messenger),
but I can connect to MSN thru Adium just after close the Messenger...