Try removing and then reinstalling Windows Live Messenger.
Note: It's listed under Windows Live Essentials in Add/Remove Programs.
Also in Control Panel > Add/Remove Programs, Messenger Plus! Live has a 'Repair Messenger' button, try using that.
Make sure no other applications are conflicting, including any add-ons or security software (firewall, anti-virus, etc.). Remove them.
If no luck, perform a clean install
which will remove all of Messenger's files and settings.