I don't know if you guys tried this yet but here goes;
Locate the folders below and delete all the files and folders inside them.
C:\Users\<Windows login name>\Contacts\ (delete all files/folders in here)
C:\Users\<Windows login name>\AppData\Local\Microsoft\Windows Live Contacts\ (delete all files/folders in here)
If you can't see these, you'd have to enable show hidden files and folders and clear the Hide extensions for known file types check box.
Try to sign in to Messenger
If you have AVG 8.0+ software’s Web Shield component
In the AVG User Interface double-click on the Web Shield component
Switch on the Instant Messaging tab
Uncheck the Instant Messaging protection option
Click the Save Changes button
Try to sign in to Messenger again
If the issue persists please try to deactivate the Web Shield component completely. If it’s still not possible to connect to the Windows Live Messenger service and the AVG Firewall component is installed in the AVG program, please check its settings.
Hope this helps