I had the same problem and I tried everything I found in all kind of forums but nothing every seems to work. What it worked for me was:
First:
Clear your proxy settings in Internet Explorer:
- Start Internet Explorer.
- On the Tools menu, click Internet Options.
- On the Connections tab, click LAN Settings.
- Clear the Automatically detect settings check box.
- Click OK, and then click OK again.
Then:
Check Internet Explorer security settings:
- Start Internet Explorer.
- On the Tools menu, click Internet Options.
- On the Advanced tab, in the Security section, make sure that the Check for server certificate revocation check box is cleared. Also, make sure that the Use SSL 2.0 and the Use SSL 3.0 check boxes are selected.
- Click OK.
Apply Changes. Close Internet Explorer
Run Windows Live Messenger and You Are Ready To Chat Again!!
Source