Buscando por Google estas cosas se consigue todo.
Como habeis dicho, debeis entrar en vuestro Router, la mayoria de las veces, ponemos esta IP en el navegador ya nos vale:
192.168.1.1
o bien:
192.168.0.1
Buscamos el apartado de abrir puertos, que se puede llamar de distintas formas, como NAT, Aplicaciones y juegos entre otros..
Una vez encontrado el apartado, debeis abrir el puerto 88 y 3074 a la IP que usa la Xbox.
Si por ejemplo usa esta IP la consola "192.168.1.10" pues debeis abrirlos a esta IP, eso si, si teneis DHCP... (que coja la IP automatica) no funcionará.
Aun así, hay cientos de hilos con lo mismo, y si no os sirve de ayuda siempre podeis acudir a Webs como Adslzone o Adslayuda en el que tienen tutoriales para muchos routers.