conectandola directamente a la red no te deberia de fallar en la primera prueba.. es raro revisa eso porque puede que algo ande mal.
Pon el modelo del router que eso tambien ayuda.
Yo te cuento mi experiencia con esto de la nat. Yo tengo un router xavi7868 de timofonica, como dices, abri 88 udp y 3074 tcp/udp,
como a ti, a mi tambien me decia que seguia teniendo la nat restringida... :S Probe a poner en el terminal de windows mediante telnet el comando upnp enable (un comando para mi router), no funciono, y al final lo que hice fue un DMZ a la direccion ip de mi xbox y funciono!! el unico problemilla que me dio es que cada vez que encendia y apagaba la xbox no me conectaba al live, tenia que hacer antes la prueba y conectarla, asi que puse la ip y dns manualmente en la xbox y problema resuelto. Conclusion, prueba lo del dmz a la ip correspondiente y mira a ver si te funciona.
saludos