You mentioned that even with softphones ext-to-ext calls fails, so lets put STUN aside just for now.
You also mentioned that there is another PBX on the same network, generally that's not a good idea unless you know exactly how to set things up to avoid any conflicts or at the very least have them on separate public IPs and segregate the traffic accordingly.
Run a firewall test on the PBX and ensure that everything passes first, it may be the case that neither STUN phones nor soft clients can communicate properly with the PBX on the first place, and we can take it from there