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.
Source/more information.
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.
