That error message occurs when there are issues with the .NET Messenger service.
This means that potentially the server WLM is trying to contact isn't online, you are facing a firewall/connection issue or some files / settings are corrupt.
Since you say you've checked Windows firewall and reinstalled, I'm going to give you some "quick" (and perhaps) solutions.
1. Press the Start button and select "Run". (If you're using Windows Vista, you have to enter "Run" in the search field, that way you can launch it.)
2. Enter the following line into the field in the newly opened "Run" window.
code:
regsvr32 softpub.dll Wintrust.dll Initpki.dll Rsaenh.dll Mssip32.dll Cryptdlg.dll Dssenh.dll Gpkcsp.dll Slbcsp.dll Sccbase.dll
3. Press your "Enter" key. If you receive any errors, feel free to post them here.