During the 1990s, GPS employed a feature called Selective Availability that intentionally degraded civilian accuracy on a global basis. Perhaps this is where/when the folks in French Polynesia got their experience. In May 2000, at the direction of President Bill Clinton, the U.S. government ended its use of Selective Availability in order to make GPS more responsive to civil and commercial users worldwide.
Today, the government commits to broadcasting the GPS signal in space with a global average user range error (URE) of ≤7.8 m (25.6 ft.), with 95% probability. Actual performance exceeds the specification. On May 11, 2016, the global average URE was ≤0.715 m (2.3 ft.), 95% of the time.
To be clear, URE is not user accuracy. User accuracy depends on a combination of satellite geometry, URE, and local factors such as signal blockage, atmospheric conditions, and receiver design features/quality.
I copied this from the government website:
GPS.gov: GPS Accuracy which contains a lot of interesting tidbits that should give you more confidence in your Nautilus purchase.
By the way, there are other countries that have their own satellites with GPS systems. I can't speak to the relative accuracy of those devices.