It sounds like a port required open for multiplayer is blocked.

Ports can be blocked by: Windows Firewall, your antivirus programs, other anti-malware programs, your Router if you have one and in rare cases by your internet service provider.

Try make sure all required ports for playing the game is open.
The list of ports can be found here:
http://support.microsoft.com/kb/917714