I've found some people in a Messenger discussion group who seem to be having the same problem as you guys.
There was a fix posted that worked for all who had posted with the problem, so it may work for you too:
1. Hit "run" in the start menu
2. Type "regedit"
3. Open "HKEY_CURRENT_USER\Software\Microsoft\MSNMessenger"
4. Delete the folder called MSN Messenger
5. After this MSN Messenger Live will login as normal.
or...
If you're not comfortable editing the registry, you can run this small reg. file posted by
Jonathan Kay [MVP] which does the same thing as posted above:
Remove Messenger Settings
/ 
