If the host is being selected based on a combination of ping time and available upload bandwidth, then it could very well be that those with moderate NAT, or even worst strict NAT are picked if they meet the ping/upload requirements.
Finally, that being the case surely there's got to be a quick fix (NAT type check before dishing out host) which would result in us peasants revolting a lot less!