A mi me pasa exactamente lo mismo. Tengo un router 3com 812 y no me detecta la xbox.
No lo he conseguido solucionar, pero como tenia dos tarjetas de red, pues he conectado la xbox a esa segunta tarjeta mediante un cable cruzado, y he creado un bridge entre las dos tarjetas de red.
Con eso ya he podido jugar, pero repito que con el router no he sido capaz.
Saludos: Siem
PD: Hace tiempo lancé un hilo con el nombre "failed autoconfig" que hablaba de mi experiencia con el router. Por si lo quieres leer.