It’s probably a firewall or router issue. Try to have them turn off their firewall. If that doesn’t work. They have to do some portforwarding.
For troubleshooting perhaps it’s easier to use a tool such as Hamachi and have every player connect to it. You will still have to turn the firewall off or create exceptions though.
Yes, it is most likely a NAT problem. Unity’s master server does provide a facilitator that you can use for NAT punchthrough but that will not work for every NAT setup.
You should test the connection using Network.TestConnection and then depending on the result start the server with true or false as the second parameter.