No tengo mucho tiempo, pero en resumidas cuentas lo que debéis hacer es:
Activar el DMZ para la IP de la consola, y ésta debe ser estática, es decir, en la configuración de internet de la consola debéis ponerla de forma manual y no automática.
Así abrís TODOS los puertos para la consola y ya tendréis NAT Abierta para ese juego y todos los demás, se acabarán los problemas de conexión entre vosotros.