I've been doing the Panthenon (or whatever they are called) games a lot lately and so far it's always been against the AI. This is fine, except when I do get matched against other players I end up just sitting at "Waiting for NAT Traversal to begin." indefinately.
Sometimes it will say something else (don't remember what) and my name will go red but that will go away and it'll be back to "Waiting for NAT Traversal to begin."
I ran the tool for setting the ports (in the Demigod/bin directory) and opened those ports in my router firewall (no Windows Firewall).