Just curious...you say you are running an Open NAT. Assuming that is on one console, how about the other?
With multiple consoles on the same public IP, you need to be running UPnP. Now if both consoles have their own public IP address that would be different, and there may be something that needs to be investigated with how that is being managed perhaps. You shouldn't be able to run a truly open NAT type to multiple consoles at the same time if you are sharing one public IP address. Why UPnP is needed to avoid conflicts that can happen with manual port forwarding/DMZ approaches. You can't forward the same port range to both consoles at once. UPnP should negotiate specific ports for each system, avoiding conflicts.