Surely they would have just noticed a discrepancy in timing and added a few circles-upon-circles to effectively fix it up? Is deeply grokking relativity necessary for GPS to work?

On the other hand, it would be impossible to make those adjustments without someone coming up with GR :-)