I have the same problem intermittently with a Netgear DG834PN Router. Sometimes I receive different error codes. The Troubleshooter doesn't find any problems (although occasionally it says that the Default Gateways are a problem, but it can't fix them).
I set the 'Open IM ports' in the Router to ON and still no luck.
Then, after much Googling, I found that newer versions of WLM require
port 1863 to be open for Inbound services.
(In my router, I have to create a Service and then open the port for Inbound services in the Firewall Rules page.)
After doing this and restarting Messenger WLM worked fine for about 2 weeks.
However, one day Messenger stopped working again providing different error codes each time. I couldn't find ANY suggestions on what to do, so I decided to play around in the Router.
Eventually I decided to try opening the same port (1863) for Outbound services AS WELL as Inbound. This worked for about another 2 weeks.
However, once again Messenger stopped working
, so I decided to try closing the Outbound port (1863) again. This works (for the moment).
Reply here if you have any questions about this.