Hast du der Xbox360 eine Statische IP-Adresse (fix, manuell statt automatisch) vegeben?
Falls nicht, gibt der Xbox360 eine statische IP-Adresse und leite dann die Ports auf diese IP-Adresse weiter.
z.B. bei einem Centro Grande Router von Swisscom:
- IP-Adresse: 192.168.1.158
- Subnetz Maske: 255.255.255.0
- Standard Gateway: 192.168.1.1
Ausserdem musst du unbedingt die DNS-Einstellungen vornehmen:
- Primär: 192.168.1.1
- Sekundär: 8.8.8.8
Wie das funktioniert ist hier erklärt: How to set up a static IP address on your Xbox 360 (extern, Englisch)
Folgende Ports müssen für LIVE Von Xbox LIVE verwendeter Netzwerkanschluss geöffnet werden:
Für den Netopia Router von Swisscom ist ist dies hier beschrieben: Xbox Live - Netopia 3346N-VGx
(Kann als Vorlage verwendet werden).
Centro Grande:
1) WebGUI (http://192.168.1.1)) öffnen und anmelden.
2) Einstellungen / Netzwerk / Port-Weiterleitung
3) Dienst ==> "Neuen Dienst hinzufügen"

Eingeben & "Speichern" klicken.
4) Dienst der Xbox 360 (andere IP-Adresse oder Hostname auswählen, als im Beispiel...) zuordnen:

Grundsätzlich immer "Speichern" klicken, damit die Einstellungen übernommen werden...
Tut's?
Nachtrag: Möglicherweise hilft dieser Microsoft Artikel: Fehler: Ihr NAT-Typ ist strikt (oder gemäßigt)