No creo que sea problema del Router, vamos por partes (aunque hay 100.000.000 de hilos hablando de esto xD)
Lo primero, quitaria el apartado DHCP del router si lo tienes activado, esta función lo que hace es asignarte una IP de forma automatica y aleatoria a todas las maquinas que estan conectadas al router (PC's, PDA's, X360, PS3 etc...) por lo tanto para abrir los puertos es más jodio.
Una vez desactivado el DHCP, vamos al apartado:
Advanced Setup - NAT - Virtual Servers
Allí le damos a "ADD" (añadir)
Y abrimos los puertos "88" y "3074" (tanto en TCP como en UDP) y colocamos la IP de la X360 (pongamos de ejemplo esta: 192.168.1.36)
Una vez echo esto, vamos a la configuración de red de la X360:
en IP colocamos (ejemplo): 192.168.1.36
Mascara Subred: 255.255.255.0
Puerta de Enlace: 192.168.1.1
DNS: 80.58.0.33
DNS2: 80.58.32.97
Si haces todo esto al pie la de la letra, tendrás NAT disponible para siempre...
PD: Que conste que te he ayudado por que me lo has dicho en pruebas, la verdad es que toy un poco harto de repetir siempre lo mismo xDDDD
Un saludo y nos cuentas