I also have this problem.
It started after I had run a perfectly good version of MSN 7.0 and finally got sick of Microsoft's messages telling me to update my msn every week so I installed Windows Live Messenger. Now, MSN doesn't work at all. I've uninstalled and reinstalled, restarted and all that jazz. Web Msn works, and my accounts work on other computers. The only thing that has changed is that i downloaded WLM.
Further, the Windows troubleshooter told me it was probably a firewall problem, I'm not running a firewall... I have the XP firewall like everyone else, but that doesn't do anything. Again stressing that nothing else has changed other than the fact I went from a working MSN 7 to a non-functional WLM v8.0
Suggestions?