It sounds like your router could be blocking access to the ports used for Messenger on all your devices, as confirmed on
AVForums.
Try going into your router settings and unblock the "Sign in to the Messenger service" ports stated here:
http://support.microsoft.com/kb/927847