That the pulsars move relative to each other (and us) is true - but this is an extremely minor point. The pulsars all have very large masses, which means it would take something HUGE to alter their trajectory significantly. Until that happens, that large mass translates to very predictable movement.
The periodicity of the pulsar is more problematic. With a sudden introduction of mass, or a sudden readjustment in the matter of the pulsar, the frequency can abruptly change. And yet, this isn't even so much of an issue. The pulsars will be monitored from some location (Earth or otherwise), and changes to their behaviour can be uploaded to the Galactic Positioning System receivers shortly after the change is observed. The receivers might compute positions incorrectly in the interim, but more likely "dead reckoning", combined with other pulsar observations could be used to determine the erroneous input, and ignore it until the update.
A more serious "flaw" is that the pulsar emissions are not (at first blush) "marked" with an emission time. One pulse looks more or less like the next. If a pulse occurs once-a-second, this translates to 300,000 km between pulse fronts. If your positioning space exceeds this length, you might end up with ambiguity in your resulting position calculation. The other 3 pulsars will provide constraints, making certain "single pulse off-by-one" errors easily discarded. But as your location space grows, it becomes more than possible for multiple location solutions to a given set of pulse-front timings. With Earth's GPS system, each satellite's transmission is coded with both a satellite identifier and timing information, making this type of error impossible.
