Depends on which side's NAT protocol is the issue. What you say suggests that your NAT is where the connections fail.
Don't quote me on this, but I think a single IP behind a router shouldn't cause NAT issues.
The only proven alternative that I know of is port forwarding from the router's settings, which requires you to know which ports the game uses for connections that are failing.
