This is also a WAG but I had an old Garmin handheld that did something like this. It had an internal battery that stored the GPS almanac when the 'main' batteries died.
After several years that internal battery died so every time I replaced the AAs in it I'd have to wait for it to rebuild the almanac. Garmin told me the almanac is basically a list of the GPS satellites the unit uses to figure out where it is.
I just Googled it and found this article that says it can take up to 12.5 minutes to get the unit working:
http://en.wikipedia.org/wiki/GPS_sig...gation_message