This was not a firewall issue for me. I already added an exemption into the firewall, and after a recent update I could not connect to the online service at all. Through some poking around I discovered in my case the culprit was HIPS (apparently exploit blocker). Which seems odd to me. I stumbled across this when I found that my game would work with overall protection disabled and the firewall up, but not vice versa.