So could we deploy, say, the first three satellites that use a modified version of GPS at first that allows you to get a very slow, inaccurate fix, but a fix nonetheless?
On Earth, similar systems were used for the TRANSIT satellites, and the Cospas-SARSat program. The latter is really cool, as it used weather satellites in low earth orbit to find a person in distress, using a cheap transmitter that's placed on a plane, boat, or very famously, Richard Branson's watch.
The way it works is that the device transmits a very stable frequency. (Perhaps modulated by the identity of the person in trouble part of the time.) As the satellite passes by, it relays the signal to the ground in a way that preserves the doppler shift. When you know the position of the satellite and the doppler shift, you can know the closest point and the distance from it.
After a few passes of your one satellite (or multiple satellites, if you have them), you can get a location that's good enough to start search and rescue.
Of course, time has passed since this was designed in the 70s and early 80s, and now GPS has fallen in price to the point where it's everywhere. So now, the devices send GPS coordinates with the identity info.
However, that does bring up an interesting idea. Maybe rovers could navigate using the position of the stars? It doesn't require you to launch 4+ GPS satellites into martian orbit.
TL;DR you need to see the stars and you need to know what time it is
Mars is fifty million kilometers away. A GPS reliever on Mars looking for Earth satellites wouldn't be able to hear anything.