Holas; deciros que yo tenía el mismo problema, y lo solucioné de la siguiente manera.
1- Lo primero, bajarse un firmware que sea compatible con la NAT Abierta, en mi caso es la v.3.40, os lo podéis descargar desde aquí
Actualizáis el router desde el System Manteinance, una vez habéis entrado desde el Internet Explorer en 192.168.1.1
2- En windows, inicio + ejecutar y pones cmd más intro
una vez dentro de la ventana de msdos pones:
3.- telnet 192.168.1.1
escribes el password.
4.- Te vas a opción 24, system maintenance y despues a la opción 8, command interpreter mode.
5.- Escribes: ip nat cone 2
6.- Te sales y haz un test en la conexión xbox live a ver si te sale ahora disponible.