I'm not at all sure how these things work exactly, but it sounds like the background service isn't running, or is locked up for some reason. Have you tried the very latest version of windows live messenger?(that's what they call "MSN" these days). You should also check windows update for any updates to your OS or, specifically, to the '.NET framework'.

If all else fails, you can always go to ebuddy.com, or somewhere similar, that allows you to sign into your IM account.

So,
1. Go to microsoft.com and find windows live messenger (the latest version). Install it, but don't try it yet...
2. Check windows update first, and install all updates that it lists there. Then....
3. Try Live Messenger.
4. If it still doesn't work, use a web based IM service until someone smarter than me comes along and tells you what the problem is.