Try importing the attached reg file. This is reset the handshaking cache. If you tried to login during a WLM downtime it is possible that this cache has been corrupted.
Another option is to delete the Application Data located at:
code:
%APPDATA%\Microsoft\MSN Messenger
(You can type this in the address bar and will be redirected to the proper directory).
Then delete all the subfolders.
Please note that you will lose all your custom content.