I had the same problem and couldnt find anything online about it (apart from this thread) so I thought I would post how I sorted it out for all those who are getting this problem.
If you use OnSpeed ( it speeds up your internet connection apparently by 5x ) the messenger gamesdo not like this (I think its the way it re routes through a proxy server) Whatever the reason it works when I close down onspeed.
I hope it helps somebody
