Comprueba que no tengas algún sistema de seguridad extra en el router, como el filtrado Mac o asi; y despúes mira si la Xbox te detecta correctamente la Red, sobre todo la configuración de la clave (Wep, WPA, WPA2 y si estas ultimas son AES o TKIP) pues quizás el adaptador de la Xbox no sea compatible con según que niveles de seguridad.
Salu2