Mal ein bisschen Off-Topic:
Viele von uns haben ja Probleme, sich mit bestimmten anderen Usern zu verbinden - sei es eine Party oder eine Left 4 Dead Runde. Mich betrifft das Problem ja auch. In der Regel liegt das Problem an nem schlechten NAT.
Vorneweg, ich bin absolut kein Experte für sowas und hab mir alles nur bei Google angelesen. Bei mir funktioniert es jetzt, hoffe aber mal dass ich meinen Router nicht total hackeranfällig gemacht hab

Und ich werde keine Fragen beantworten können falls was nicht so läuft wie geplant...
Diejenigen die Probleme haben sollten mal ihren NAT Typ checken. Dazu auf (sorry, mein Dashboard ist englisch) My Xbox, dann ganz nach rechts und auf Network Settings gehen. Dann mal Test Xbox Live Connection ausführen. Entweder geht der Test reibungslos durch, dann habt Ihr nen offenen NAT Typ und alles ist toll - und wenn ihr nicht verbinden könnt liegt es wohl an der anderen Seite...
Wenn im letzten Teil ein Fehler auftaucht, dann fragt mal die weiteren Infos ab, dann kommt wahrscheinlich dass der NAT Typ strikt oder gemäßigt ist. Folgendermaßen kann man das nun umgehen
a) Ihr öffnet in Eurem Router die folgenden Ports:
TCP 80
UDP 88
UDP 3074
TCP 3074
UDP 53
TCP 53
Das hat bei mir dazu geführt, dass ich von NAT Strikt auf moderat gekommen bin.
b) Was bei mir das NAT "geöffnet" hat, war es eine DMZ (Demilitarisierte Zone) im Router einzurichten. Dazu tragt Ihr die IP Adresse Eurer Xbox in den Router als DMZ ein. Soweit ich richtig verstanden habe, werden dann für diese Adresse alle Ports geöffnet. Damit hat es bei mir funktioniert. Hoffe wie gesagt nur, dass ich damit nicht alle möglichen Hackerangriffe abkriege
Hoffe es hilft paar von Euch und wir haben etwas reibungslosere Verbindungen!