Here's an interesting article[1] about how relativity affects GPS satellites. The clock ticks in a GPS satellite need to be accurate to within 20-30 nanoseconds for accuracy, and they tick 38 microseconds/day faster to account for relativity.
GPS is one of the few technologies that have to account for both Special Relativity and General Relativity. The level of engineering that went into the system is just amazing.
Fun fact, GPS satellites use rubidium clocks instead of cesium clocks, and only maintain their accuracy thanks to yet another incredible feat of engineering.
What if all the satellites are off by the same amount?
According to the link posted higher up in the thread, in early 2016 they were all off by 13 microseconds for 12 hours, with no apparent consequences for anything ordinary people use GPS for such as location finding.
To triangulate, I think you need to know (1) where the satellites are, and (2) how far you are from each satellite. I think either absolute distance or relative distance works.
Getting both of these depends on knowing the time. That time comes from the satellites. Let's say they are all off by 1 us. Your time is derived from satellite time. That would mean the time you use to look up/calculate their positions will be off by 1 us from the correct time so you would get the wrong position for the satellites.
A quick Googling says the satellites orbital speed is 14000 km/hr, so using a time off by 1 us to look up/calculate satellite position would give you a position that is about 4 mm off.
The procedure for deriving the time from the satellites would get some extra error from this, but that should be limited to about the time it takes like to travel 4 mm, so we can ignore that. As a result your distance measurements between you and satellites would be off by about 4 mm or less.
The key here is that when all the satellites have the same error, the time you derive has the same error, so your distance calculations should still work, and so you only get an error of about how far satellites move in an interval equal to the time error.
In summary, if all the satellites are off by 1 us, your triangulation seems like it would be about 4 mm more uncertain.
If only one satellite is off, it is going to depend on how the time algorithm works. If the algorithm is such that it ends up with a time much closer to the times of the correct satellites than to the off satellite, then if it calculates the distance from the triangulated position to the expected positions of the satellites, and compares that to the measured distance, it should find that one is off by something on the order of the distance light travels in 1 us, and the others are all pretty close to where they should be. It should then be able to figure out that it has one unreliable satellite it, drop it, and then get the right location.
I have no idea if they actually take those kinds of precautions, though.
The case that would really screw it up would be if several satellites are off, but by different amounts. With enough observation it should be possible in many cases to even straighten that out, but it might be too complicated or too time consuming to be practical. (This is assuming that the error is that the satellites are simply set to the wrong time, but that wrong time is ticking at the right rate).
Precise geolocation relies on extreme time accuracy (the story always being that relativistic time dilation effects with the difference in gravity on the surface vs LEO must be accounted for), so yeah, it wouldn't surprise me one bit that the accuracy required is on the order of much less than a millisecond.
[1] http://www.astronomy.ohio-state.edu/~pogge/Ast162/Unit5/gps....