My GPS locks up to satellites very quickly when I am not moving the car.
However,  when the car is moving and I turn on the GPS,  it may take several minutes to lock.  Why is that?

Answer:
A GPS that has been off for more than some short length of time must receive a complete navigation message from at least four different satellites before it can achieve 3D lock  and  start  tracking  your  position.  When your vehicle is sitting still and/or you are "out in the clear" with a good view of the sky, the signals received by your GPS from the satellites are relatively stable.

However,  when you are moving the car or  walking along with your GPS,  you may be:   making turns,  traveling under trees,  in and out of the shadow of tall buildings,  going under highway underpasses,  passing large trucks and other reflecting and signal blocking objects.  Walking or driving along under trees or in mountains,  or when you are making frequent turns,  you may be causing the GPS signal to "come and go" thus disrupting the continuous flow of data to your GPS from a particular satellite.   Any of these events and objects can cause your GPS signal to "flutter" and become momentarily unreadable.  When this happens,  your GPS fails to receive all  of the data bits needed to lock during a single navigation message transmission.  When this happens,  the GPS must attempt to receive these 30 second message streams over and over until  it has collected navigation messages from at least four GPS satellites  error free.   This can take a LONG TIME if the signal flutter is bad enough.

Compared to the newer 12 channel parallel receivers,  the older single channel multiplexing GPS receivers (such as the Garmin 45/40/38 series,  and dual channel receivers (such as Magellan GPS 2000/3000/4000,  the Magellan Pioneer and GPS 300) are much more prone to problems locking when the signal is "chopped"  (by trees,  buildings,  mountains,  multipath reflections, etc.).  This is because the scanning receivers must have at least 2 or  4 times more "error free signal listening time" than the parallel 12 channel receivers to achieve error free data from 4 SVs.

Some additional data:
The  satellites  broadcast  two  types  of  data,   Almanac   and  Ephemeris.   Almanac  data is course orbital parameters  for  all SVs.  Each SV broadcasts Almanac data for ALL SVs.  This  Almanac data  is  not  very precise and is considered  valid  for  up  to  several  months.   Ephemeris data by comparison is  very  precise orbital  and  clock correction for each SV and is  necessary  for  precise  positioning.  EACH SV broadcasts ONLY its own  Ephemeris data.   This data is valid for a period of time  (maybe several hours) as determined by information contained in the broadcast.  The Ephemeris data is broadcast by each SV every 30 seconds.

Joe Mehaffey