Well, it sounds like port forwarding on the router is the issue. I don't know anything about the XBOX, and it's going to depend on the specific games you're using I would imagine. Here's a sample of port for some games using a Netgear router, the ports are the same for any router, but obviously the port forwarding instructions would be different.
http://kbserver.netgear.com/kb_web_files/N100495.asp
http://kbserver.netgear.com/kb_web_files/N100495.asp