Just a hunch, but can you access any secure sites?
Try going to
https://www.paypal.com/ and see if that works.
Hotmail uses a secure connection to login and I've had a client that experienced this before, albeit with AOL. In the end it came down to the MTU setting, but then, this should be set properly now in your case?