Hola, pues seguramente sea algun fallo en la configuración del router (abriste los puertos para Xbox Live?).
Mira haber si tienes algún tipo de protección extra (como el filtrado Mac, o el SSID oculto), y si no es así, prueba a cambiar la configuración de la 360, poniendo los datos manualmente, mira el rango de Ips que da el router, y el resto sácalos desde algún PC que tengas conectado por Wifi (DNS, Getaway... etc).
Y si aun así te sigue sin funcionar, quizás sea algún tipo de incompatibilidad de dicho router con Xbox Live, pero eso ya no te lo podria asegurar.
Salu2