This is due to the architecture of the Internet and affects any software trying to make connections. Your only options are either:
a) run a TURN server and pay for the bandwidth costs of relaying all traffic for the users who cannot directly connect (this is what services like Skype do to work around it)
b) wait for the IPv6 rollout which should alleviate the worst cases of NAT by having a much larger set of available addresses.