Beside possible problems mentioned by Boki, I came across few situations where there was some kind of FM transmitter active in vehicle (CB radio, audio transmitter to amplifier, ...) which generates strong radio signal interfering with GPS signal.
Turning off such device solved problem.