es raro, si tienes puesta la configuración de red de forma automática prueba a ponerlo estático.
normalmente los routers tienen la ip 192.168.1.1
configuración de xbox 360
ip. 192.168.1.40
máscara de subred 255.255.255.0
puerta de enlace 192.168.1.1
DNS Telefónica: 80.58.0.33 y 80.58.32.97
si sigue fallando pues comprueba si has actualizado el firmware del router ya que hay algunos routers que son incompatibles mira por casualidad sale en esta lista: http://www.xbox.com/en-US/live/connect/routerlanding.htm