Did any of the other games you tried use peer to peer connections, or did they have servers for multiplayer?
Can you try connecting one or both of the PS4s directly to the modem, bypassing the router, or place the PS4 in the DMZ of the router?
Can you try a wired connection if you are using wireless, or vise versa?