When you go to internet explorer and click file does it have a tick next to "work offline"? If so untick it.
Upgrade to the latest version of Windows Messenger, if you are not already using it,
Click Here to download Windows Messenger 5.1
Does this problem also happen with MSN Messenger, or just Windows Messenger (try MSN Messenger if you haven't already to see if the problem is actually caused by Windows Messenger).
If you are using a firewall, make sure it allows Windows Messenger full access to the internet. Also that you are using the latest version of the firewall.
Are you using a proxy to connect to the internet?