Comprueba que tienes todos los puertos relacionados con Xbox abiertos y dirigidos a la IP de la consola (y cuando digo todos, digo todos, no solo los típicos 88 y 3074). Además, sería buena idea actualizar el firmware de tu router a la última versión. A mi esto que dices me pasó hará un mes y en el SAT directamente se lavan las manos (y yo tenía los puertos abiertos menos uno, el 5XXX creo, con NAT disponible, etc.). Nunca averigüé porqué ocurrió, pero se que actualizando el firm del router y abriendo el puerto que me faltaba, volvió a funcionar correctamente.
y luego aplica el modo DMZ hacia esa IP, y ya tendrá todo abierto.