Shoutbox

Sounds like something is blocking them.

Anti-virus? Firewall? Disable them, then try. Or if you can, add Windows Live Messenger onto the exception lists.

If you're using a router, try unblocking the ports. You can also go to PortForward.com, click the router you have (you'll have to find the make and model number), then MSN Messenger, and it'll give you instructions. However, I'd use the ports in the first link, as they're more updated for the new Windows Live Messenger.