Hey, just want to put my findings in here aswell.
Netgear DG834 ADSL router.
Running the router in Bridge mode (every PC can connect to the DSL account as you would with dial-up, no port forwarding needed, firewalls needed on every machine), the connection info window finds the players and starts connecting to them. Great, this works.
Running the router in Router mode (the router connects to the ADSL account and PCs use the router as their gateway), the ports forwarded correctly (I was generous to test, port 6000-6200 TCP/UDP), I get the "Cannot connect to NAT facilitator" message.
I turned on logging for that port forward rule, so that whenever the rule is even taken into consideration, it will appear in the routers logs. Try connect to a custom game in demigod, get the NAT facilitator error message again. I take a look at the routers logs. Empty. *puzzled*. I know the router logs work, since I've debugged issues with them before, but this just baffles me. NO TCP/UDP packets between ports 6000-6200 were even considered to be port forwarded.
Soooo, whats next. I take a look at Demigod's connections in Netlimiter when trying to join a custom game and see the following:
126.96.36.199:6000 appears under its connections, but then terminates unexpectadly. I suspect this is the problem. Which is the same conclusion you came to Spooky.