A mi me pasaba lo mismo semanas atrás.
tenia NAT disponible y en el matchmaking tenia porblemas para encontrar partidas y se me desconectaba del live.
¿el problema? Pues era mi Obsoleto Router, un Zyxel prestige 643 de telefónica de hace unos...casi 5 años, pese a tener todos los puertos y todo configurado correctamente el router no era compatible o no tenia la tecnologia para que el live rulase correctamente.
Ahora, tras adquirir un nuevo router-modem y configurarlo correctamente, gozo de una Nat disponible y un total y perfecto acceso al servicio XboxLive, como debe de ser cojoné !