A mi me pasó el Jueves, lo mismo que tu comentas, me conectaba al Live, pero no me daba NAT solo error de que no encontraba la IP y daba error de TEREDO.
Lo curioso es que con el juego Gears of wars 4 me dejaba jugar Online mientras me daba el error de TEREDO, pero juegos como Forza Motosport, Forza Horizon 3 o Call Of Duty Modern Infinite Warfare o me daban fallo de conexion o directamente no me encontraban partida.
Por la mañana llamé al SAT de Xbox y me dijeron que abriese los puertos del Router (Livebox negro, fibra 300) y que se solucionaria.
Seguia sin poder conectarme y llamé a Orange donde me dijeron que eran que IPv6 era el problema y que si queria una IP fija para solucionarlo.
Llame de nuevo a Xbox y me dijeron que era problemas del servidor y que llevaban con el sistema parcialmente caido, me remitieron a que llamara más tarde.
A las dos horas llamé de nuevo al SAT de Xbox y justo haciendo las pruebas con el técnico me salió NAT Abierta, hasta ahora.