Would GPS work in a (locally) newtonian universe? Often, when there are question on why fundamental research makes sense or is neccesary, I've seen answers like "GPS is used everywhere today, and it wouldn't work without relativity".
Of course, if we didn't know about relativity - basically, if we still assumed physics was newtonian - and built a GPS system around this assumption, it wouldn't work in the "real world". We'd be terribly puzzled why those clocks that worked so well on earth suddenly ran faster on a satellite.
However, assuming we had a newtonian universe, with the speed of light being finite, and clocks running at the same speed no matter how far down a gravity well they are - is there any reason why we wouldn't be able to build a GPS system? Except of course, that that kind of universe wouldn't work at all so the human species couldn't have developed?
What the question boils down to is, I guess - is the fact that our universe is relativistic that's needed to build a GPS system, or is it just the fact that we know about relativity?
Please notice that this isn't a duplicate of Why does GPS depend on relativity?; that question asks why we need to correct for relativistic effects, while I'm asking if/why GPS isn't able to work in a world that doesn't have them.
 A: 
is there any reason why we wouldn't be able to build a GPS system? 

No, there isn't.

is the fact that our universe is relativistic that's needed to build a GPS system, or is it just the fact that we know about relativity?

The only reason we need to know about relativity to build a working GPS system is so we can correct for its effects on the 'newtonian' flat-spacetime, finite-speed-of-light background you'd assume otherwise. If those effects were not present, then we wouldn't need to correct for them, and building a GPS system would be (eeever so slightly) easier.
A: Actually, this has been done. It was called LORAN. All the sources were fixed and near sea-level (where the receivers were too--we hope, as they were boats and ships)--and the Rx velocities were much less than $c$.
A: GPS works by comparing the time it takes for time and position stamped signals emitted by satellites to arrive to your location. If you know the speed at which the signal propagates, you know how far you are from each signal source, and using multiple sources, you can determine your position by intersecting circles centered on each satellite. Each circle represents where you could be relative to each satellite based on the propagation time information. Note that so far, we have not used any relativistic effect. We just need to determine how fast the signals propagates between you and the satellites. For that to work, you need a finite propagation speed. If the signal propagate instantaneously from the satellites to your position, this would not work. 
For GPS, you are using electromagnetic waves, but a similar system can work using any other type of signal, for example sound waves (not from space obviously). If you are in a room and have speakers at each corner emitting ultrasound signals (for better resolution) that are position and time stamped in any manner, you can use the same techniques as in GPS to determine your position, if you know the propagation speed with enough precision. So, as you see, relativity is not absolutely required to build a GPS. 
However, there is one thing that relativity helps with. You know that the propagation speed of your signal is the same all the time. It does not depend on whether the satellite is going towards you or away from you. That helps a lot. In theory, you could compensate for this type of effect using Doppler frequency shift. I don't know how practical that would be though.
A: Abandoning a relativistic universe makes it difficult to understand what to do with the speed of light.  Why doesn't light go faster when the transmitting object is moving toward the observer?  What is the reference against which this finite speed is measured?  Prior to relativity, it was assumed that the speed of light was relative to some type of medium, the aether.  
In a Newtonian universe with light moving at a fixed speed through aether, you'd need a model of the aether that is precise enough to calculate the propagation time through it. 
It is also possible that certain configurations or orientations of the aether would make the calculations of the signal ambiguous.
