The difference sounds like a warm start vs a cold start.
With a warm start, the GPS already knows Ephemeris data for at least 3 of the satellites above it. It can therefore kick straight off with solving the time signal equations, and can get a fix quickly. (That Ephemeris data could either come from having recently used the GPS, eg previous 4-6 hours, or could come from the network with assisted GPS)
With a cold start, the GPS doesn't know the precise location (Ephemeris data) for the satellites above it. Instead, it needs to wait until it gets a full set from the satellites above it, which means it needs between 10 and 40 seconds of error free data from them (depending where in their data cycle they all are). Once it has that, it can solve the equations and knows your location. If you're moving, or surrounded by lots of buildings, or anything else triggering interference, it can take several tries for the GPS to get an error free set of Ephemeris data from enough different satellites, which can easily mean 5-10 minutes for a lock.
More informations here and here.