Firstly, invest in a wireless router that supports UPnP. This will make your life easier.
linksys wrt54g is probably the easiest router to configure and only set you back about 50 dollars.
if not you should definitely try to get a router using a linux os and iptables as its firewall configuration.
UPnP - Universal Plug and Play: this means the router allows applications (such as your 360) to configure the ports they need forwarded.
For those of you who dont know. XBL uses port 3074 udp protocol. So you can configure this manually via your web interface if you dont have UPnP.
You can also configure this manually using ssh or telnet and iptables commands.
to do this type as root pressing enter after each line: BE SURE TO CHANGE 192.168.1.112 to your 360's ip. you can find your 360s ip under SYSTEM>NETWORK SETTINGS>EDIT SETTINGS on the dashboard
iptables -t nat -I PREROUTING -p udp -d $(nvram get wan_ipaddr) --dport 3074 -j DNAT --to 192.168.1.112:3074
iptables -I FORWARD -p udp -d 192.168.1.112 --dport 3074 -j ACCEPT
This will forward udp port 3074 from your routers internet side IP to your 360's internal IP thus allowing that port access from all hosts. if you wanted to be really anal you could add xbl's server subnet as the only ips allowed to access that port by inserting -s and xbl server ip block. but thats for the technical types and is unneeded.
Lastly if none of the above works for you or is available as an option, almost every router on the market supports dmz. DMZ is an acronym for demilitarized zone. It is supposed to be used to increase security on a network, but its positioning in between the firewall and the internet make it an easy fix for people having issues with port forwarding. Simply turn this feature on, on your router and enter the 360s ip as the host computer. And voila you should get an open nat.
Hope this helps.