Esse mesmo erro acontecia comigo quando eu convidava ou era convidado por alguns jogadores. Com outros, não acontecia. Nos consoles, diferentemente de no pc, a qualidade da conexão do multiplayer online depende da do host. O que pode estar acontecendo é que você ou seu amigo ainda não tenha desbloqueado a dificuldade na qual pretendem jogar entre si(mas não tenho certeza se existe essa necessidade nos consoles). Para isso, é necessário fazer fendas solo de acordo com o nível de dificuldade, do Suplício 7 em diante. Quanto maior o nível de dificuldade, maior o nível da fenda solo requerida.
Além disso, caso não saiba, seu tipo de NAT precisa ser 1 ou 2. Se for o 3, não conseguirá jogar multiplayer online. Para saber seu tipo de NAT no PS4, acesse Configurações > Rede > Exibir status da conexão à Internet. Pode ser que no momento que você foi jogar, a PSN estava fora do ar. Para saber se a PSN está funcionando, acesse Configurações > Rede > Exibir status dos serviços da PlayStation Network e cheque se a opção Jogos e redes sociais está ok.
Quanto aos dados do jogo, se você não tiver apagado da nuvem da PSN, ainda pode baixá-los. Conectando o console via cabo com o modem/roteador também ajuda a melhorar a conexão. Falo por experiência própria.