Ok, I had the same problem, and on mac messenger it still doesn't connect. Try these first.
1) Try logging onto a web msn client like meebo or ebuddy to make sure it isn't a problem with your msn account.
2) When you try on a pc or another account, check what the msn service says, it isn't always reliable, but sometimes it can depend on that.
3) Check that your firewall settings allow msn on both your mac and pc, including any extra firewalls such as zonealarm.
4) If the problem on the mac persists, try adium, adium for some reason allows me to connect on my mac, but not using msn for mac. Strange, I know.
5) To fix it on the pc, you should usually get an error code when the login fails, google the error code number and you should find a few fixes for it. The fixes I've found tend to require some command line input, but I have managed to temporarily fix it by clearing all my cache and cookies from the browsers I use then disconnecting and reconnecting my router. This only worked for a while on my pc only. I did however find a more permanent fix on google.
Hope these help.