To get them to work right, we have to design them to account for the predictions of relativity, rather than just classical mechanics, but if the universe ran on classical mechanics rather than relativity, I can't see any way in which it would prevent us from creating GPS devices; it seems to me that it would be even easier.

Yeah, the comic seems to be missing the mark there.

Still, if we designed them to work taking into account relativity, and the universe ran on classical mechanics, then they would not work.