I've actually been writing an application that uses GPS, so I can shed some light on this. onik is correct about the AGPS vs GPS. Additionally, though, GPS can be affected by a number of factors which can reduce accuracy or the ability to receive a signal at all:
GPS accuracy is affected by a number of factors, including satellite positions, noise in the radio signal, atmospheric conditions, and natural barriers to the signal. Noise can create an error between 1 to 10 meters and results from static or interference from something near the receiver or something on the same frequency. Objects such a mountains or buildings between the satellite and the receiver can also produce error, sometimes up to 30 meters. The most accurate determination of position occurs when the satellite and receiver have a clear view of each other and no other objects interfere.
As well with AGPS is DGPS (Differential GPS). (But I do not believe phones have this, only AGPS).
Like the AGPS, the DGPS uses a fixed GPS location (such as a cell tower) to send information to the GPS receiver. DGPS, however, looks at both the satellite and the fixed location adjusts for any difference between the two, and then sends that information to the receiver. DGPS is particularly helpful when atmospheric conditions interfere with reception.
In short, make sure you are outside and have a clear view of the sky. The initial lock will sometimes take quite a bit of time, but subsequent locks shouldn't be nearly as bad.