I had quite a few problems as well the first few times I tried to host.
And I tried all the same things that you tried.

I have a Belkin router but see if you can find something similar to these two settings on yours:
Of course, the port forwarding: http://i.imgur.com/qslmy.png
And then there's this: http://i.imgur.com/dKCEy.png

Some routers have multiple settings which they generically call 'firewall' make sure the only firewall you're running is NAT.

I did not have to enable DMZ host in order to get my server running. Everything worked peachy as soon as I turned off the extra 'firewall'.

Sidenote: Make sure windows firewall also has an exception for AoS

Edit_1:
Forgot to add that I'm running a server on Win7 Prof. 64-bit.
I haven't tried the server on linux yet. Some time next week I'm going to try running it through Wine on CentOS.

I was trying to create a server and had some serious problems. Things that i did:
1. Port Forwarding my netgear router.
2. Allowing Through my Nortan Internet Security firewall/ turned off Nortan.
3. Allowed Router to respond to pings

Things i was wondering about:
1. Does this work on 64-bit windows
2. Would Virtual Machine Linux work?
3. Does this run on Linux 64/32 ubuntu (server/client)