Also wenn du NAT schon eingerichtet hast (Port xxxx nach ip-der-xbox nach Port xxxx) und die Firewall am Router (testweise) mal ausgeschaltet hast sollte dies eigentlich klappen und sogar die beste Lösung sein.
Was du noch versuchen kannst ist zu schauen ob dein Router UPNP kann und dies aktivieren und ob es eine DMZ Einstellung gibt in der du die IP deiner XBOX eintragen kannst.
Denke die einfachen Sachen wie Harter Restart der XBOX (15 sek an der Konsole den XBOX Knopf gedrückt halten bis sie aus ist) und Neustart des Routers hast du schon probiert.
Du kannst aber auch die DNS Einstellungen manuell einstellen. Im Moment ist wahrscheinlich die IP deines Routers dort drin. Du kannst auch die deines Providers einstellen (Im Inet suchen nach z.B. Telekom DNS Server) oder die von Open DNS mal probieren:
208.67.222.222 (resolver1.opendns.com)
208.67.220.220 (resolver2.opendns.com)
208.67.222.220 (resolver3.opendns.com)
208.67.220.222 (resolver4.opendns.com)