Today I came across this issue when trying to sign in to Windows Live Messenger.
Everyone I talked to was able to sign in, though, so I tried another account and was also able to sign in.
Binging around, I found several blog posts pointing to a post in the Messenger Support blog with the solution to this problem. In my case (Windows 7 x64) the solution would be to remove the %LOCALAPPDATA%\Microsoft\Windows Live Contacts (usually C:\Users\<Windows Logon name>\AppData\Local\Microsoft\Windows Live Contacts) folder.
Instead of removing the folder, I thought of renaming it to avoid removing my contacts for all account that were able to sign in. When I tried it, I got an error stating the the folder was already being used by another application.
Since I had Windows Live Mail open and assumed it uses the same contact store, I closed it and was able to sign in to messenger with no problems.
As a developer and architect, I find it disturbing that such errors are presented to the user. The message hinted that there was a problem signing in to the server and, as it turned out, it was a problem with only one account for only one Windows user in only one machine.
So, developers and architects out there (me included), always give the user an error message meaningful to what problem he/she is running into. Adding technical data to help support is nice but should be expressly accessed by the user (Windows Live Messenger got that part right).