Try going into "Safe Mode (with Networking)" by tapping F8 continuously when starting-up your PC [
more info].
This'll just run the basic required programs, drivers and services (rather than all of them).
Run Windows Live Messenger and see if it works.
If it does, you know there's something interfering in normal Windows mode.
If no luck, see CookieRevised's guide to
Completely remove (MSN/Windows Live) Messenger.