0x81000301: The Winsock layer could not establish a connection.
First, if you don't need a proxy then don't use it.
Second, make sure that no firewall (like ZoneAlarm) is blocking your MSN Messenger connection!
Also, did you try out the build-in troubleshooter? Press the button when that errormessage shows up.
Fourth note: If you've removed spyware/adware with an automated tool (Spybot, Ad-aware etc...) it could have damaged the Winsock layer beyond normal repair.
To reinstall/fix a defective winsock layer:
Matty's reply to AHH I CANT GO ON MSN!
or use this tool to automatically do it:
http://www.iup.edu/house/resnet/winfix.shtm
If that doesn't work, and as a last resort, you can refer to:
Signing in problem (0x81000370) (works for some other errors too)
Signing in problem (0x81000302)
Signing in problem (bad cache problem)