With it, you can measure distances of several thousand km with a precision on the order of a few millimetres. The problem is that it's really expensive compared to GPS: at each site you need a reasonably size telescope, atomic clock, some serious storage, and a way to ship all the data to a central cluster.
And pulsars are quite a bit further away than tens of light minutes :) Mars is currently 14 light minutes from Earth. PSR J2144-3933 is one of the nearest known pulsars, and it's some 587 light years away.
People will happily spend an entire day becoming unlost if they're lost.
As long as they have the means to survive, they'll be willing to spend much longer than that.
Most GPS units do this in the background. But if you leave it unpowered for too long, it will need to update itself before it begins to work properly. The GPS in my dad's car used to have a flaky ROM, and it would show the car flying across the wilderness at over 400mph while it was updating.
They're talking about measuring millisecond pulsars, there's no latency
But if you're travelling significant distances, you're not going to be able to assume the space between you and all your beacons is flat.
For good accuracy you'd need a predictive spacetime curvature map for the entire galaxy, and that might not be an easy thing to generate.