I'll try to keep this brief.
A friend and I spent about 3 hours trying to connect. We tried everything you could possibly imagine.
I am running PFSENSE as my firewall.
I created all the necessary rules and my ports were open. My friend did the same. Still no workie. Long story short, I remember having had a similar problem with Supreme Commander and here is what fixes the problem:
Make sure your outbound NAT is configured to use STATIC PORTS.
I don't recall the specifics and don't feel like searching for it right now
, but to paraphrase, the problem is this: (and someone feel free to correct me if I mistate this)
PFSENSE will randomize your ports. The outbound mapping isn't static by default. It does this for security reasons as most programs are predictable in what port they will use next. Theoretically if someone could guess the next port they could spoof a packet and enter your network like a ninja. 
You could see how this could be a problem if the ports the game is using are hard coded in the packet. Apparently, you can use a variable in your packets which will allow the firewall to swap the correct ports in and out within the packet. (it keeps track of them) But SupCom and Demigod are hard coded. (as are some other games)
I know that probably doesn't make much sense to most people. I'll see if I can find the post that explains it again. It's on the pfsense forums.
For now, I'm going to bed. 