No hay nada raro en ello. En la party hay un host (el que la crea) que es el que manda al resto los datos como si de una partida online se tratase. Si el host tiene poca conexión mal asunto, por eso con otros os va y no pasa nada, porque el streaming al resto del grupo no depende de vosotros.
Probad a estar los dos en una sala de juego juntos sin nadie más, verás que os funciona. Es porque el bitrate en las salas de juego es algo menor que el de las party (creo que el de las charlas privadas es de igual calidad que el de las party)
Un saludo!
EDIT: Había entendido mal, supongo que saldréis ambos con la misma IP pública, que es algo común en las Wimax, el follón vendrá al intentar conectar uno con el otro directamente, que al tener la misma IP pública se hará un lío. Entérate si tenéis IP compartida en la misma zona.