Exit Messenger and try this:
Download and run this file:
Remove Messenger Settings.
or do it yourself (advanced)...
1. Go to Start > Run
2. Type in regedit and press enter
3. Navigate to "HKEY_CURRENT_USER\Software\Microsoft\MSNMessenger"
4. Delete the folder called MSNMessenger
After this Windows Live Messenger should login as normal.