Do you have any add-ons (SweetIM, Smiley Central, etc.) or patches?
Have you tried reinstalling Messenger?
Do you have any internet security, anti-virus or firewall which maybe be blocking it?
Try to using the Connection Troubleshooter (you don’t have to login to Messenger to do this). You can find it in Messenger -> Tools -> Options -> Connection tab
More:
Windows Live Messenger Connection Problems etc.