Buenas, eso que comentais puede ser debido a varios factores.
1º Que alguno o ambos no tengis una NAT disponible (que la tenga moderada o estricta). Esto normalmente se soluciona abriendo puertos
2º Que el host o el cliente tengan copado el canal de SUBIDA. Está mas que demostrado que para jugar decentemente es necesario tener una buena conexion de subida para los host y muy recomendable para los clientes. Lo normal es que a alguno se le "olvide" cerrar la mula y esas cosas.
Saludos.