Beim Router sollten die Ports für XBOX-Live freigegeben sein: 88 UDP,
3074 UDP und 3074 TCP.
Desweiteren kann es sein, dass Ihr Router irgendwo in den Einstellungen
über eine Option namens UPnP (Universal Plug n Play) verfügt. Diese
bitte einmal testweise abschalten. Vielleicht ist auch ein
Firmwareupdate für Ihren Router nötig.
Versuchen Sie bitte auch einmal die IP des Routers als primären
DNS-Server in der XBOX einzutragen.
Sollte es danach immernoch zu Verbindungsproblemen kommen, schauen Sie
nach ob der Router eine DMZ-Zone (Demilitarized Zone) besitzt und
schreiben Sie dort die IP-Adresse der Konsole hinein.
Es kann sich theoretisch allerdings wirklich um eine generelle
Inkompatibilität zwischen Ihrem Router und der XBOX360 handeln. Fragen
Sie bitte einfach mal beim Router-Support nach, ob dort irgendwas
bezüglich der XBOX360/XBOX bekannt ist.