Like said, a lot of those little gps receivers have a small battery to keep in memory which satellites it last locked too. That way, when started, it looks if it can find the current visible satellites first (has to be calculated, as they are not geo-stationary). This saves time.
If the battery is bad, the receiver has to look up a minimum of 24 satellites to find which it can lock to.
Open the receiver up and put a new battery in. Let us know.