Primero haced los dos la prueba de conexion a "xbox live", si a la hora de conectar , os conecta pero sale un simbolo con un tirangulo amarillo encima de la conexion, si le dais a mas informacion os dira si teneis nat, estricta o moderada.
Para solucionarlo solo teneis que abrir los puertos de xbox live, segun sea tu router o modem cambiara el como abrir esos puertos.
Saludos.