Esto se debe al sistema de phasing. Quiere decir que, según la etapa en que estáis cada uno de una misión, dejáis de ver a los que están en etapas no compatibles. Por ejemplo, si uno ha acabado la cadena de misiones y solventado un conflicto, estará en otra fase que los que todavía están luchando por traer la paz al pueblo.
En ocasiones, el problema se puede solucionar "viajando" hacia un compañero: desde la pestaña de "party" [P], o clan [G] si es un compañero de clan, o de tu lista de contactos, clic derecho en su nombre y "Travel to player"... Hay veces que no es suficiente, pero muchas veces sí permite jugar juntos.