Yo tengo tambien tengo router y me pasaba esto pero desde que abri unos puertos en el router no me ha vuelto a pasar. Haced la prueba de conexion desde el dashboard y mirar si os dice nat moderado, si os pasa esto el problema es el mismo que yo tuve.
Solo teneis que abrir en el los puertos 88 UDP y 3074 TCP/UDP a la ip de vuestra consola y la cosa funcionara bien. (si teneis puesto en la xbox que obtenga la ip automaticamente la tendreis que cambiar a estatica)
