I just helped a friend of mine fix his MSN (btw, ISL Light from www.remotedesktopsupport.com is a GREAT support tool). He kept getting connectivity errors after upgrading to Windows Live Messenger (MSN 8). It turned out that there were two main problems with his setup.
1) Firewall. He had checked the "Do not allow exceptions" checkbox in the Windows Firewall.
And most importantly:
2) His date and time weren't set correctly. Apparently, MSN won't let you connect to their servers if your computer's date and time are off. So the quick fix was to set the time and date and 10 seconds later his MSN worked like a charm.