Here are some thoughts::
Check to see if uPnP is enabled on your router. If not enable it.
--
Try setting manual/static IPs for each PS from within the router. Usually this is done via their MAC address.
--
If it still doesn't work, you can try disabling uPnP and forwarding the ports manually for each IP/MAC.
http://portforward.com/english/applications/port_forwarding/PlayStation_Network/
https://support.us.playstation.com/app/answers/detail/a_id/241/~/firewall-port-numbers-to-play-games-online
--
Another thing you could try without manually forwarding the ports, leave uPnP on, put one of the PS's in DMZ on the router.