NAT es traducción de direcciones de red.
Es un método para que máquinas con direcciones IP públicas puedan hablar con máquinas con direcciones IP privadas a través de un router con NAT. De esta manera, pese a que tu IP es privada, la gente de fuera se puede conectar a tu máquina, porque el router con NAT se encarga de hacer el trabajo.
Y ahora, a la solución.
Abre los puertos que necesites (por el foro de Online los encuentras), activa NAT en el router si existe la opción o bien pon la IP de la Xbox en la DMZ Host en caso de que el router tenga dicha opción.
En principio son soluciones complementarias. Abrir los puertos, o bien DMZ. Eso sí, verifica siempre que no esté bloqueado el tráfico WAN (precisamente el que te interesa) y que uPnP esté también activado.
Si el router tiene firewall propio, revisa el log y configúralo de manera apropiada.
