When you install games that need to connect to the internet, the first time you start it, windows will ask if you want to allow it to access the internet. It only does this once, and maybe when it did you accidentally pressed "don't allow". I know you said you checked the firewall, but make sure you set it as an exception in the firewall.
If you go to the screen where you can turn the firewall on and off, and click the exceptions tab, you can click the "add program" button, select the .exe of the game in the program files (not the shortcut), and this will allow it through the firewall. Your anti-virus software might also be blocking it, so you may have to add it to a "trusted program" list or something similar (it depends on the anti-virus).