Wattle,
I'm not sure how familiar you are with GPS, so I apologise if I'm saying things you already know. Also, I don't have a specific answer to the problems you have experienced, these are just a few tips about GPS.
I have a nokia e52, which has A-GPS. In my experience, GPS on phones is far more temperamental than on dedicated GPS devices. One of the first problems is the size of the handset, modern phones jam a lot of things inside. This creates inherent problems with the placement of all the various antennas (GPS, wifi, Bluetooth, GSM etc) and so its easy to affect the signal the phone can see by orientating the phone the wrong way, or holding the phone so your hand covers the GPS antenna.
Secondly, again due to space and power constraints, the GPS chips in mobile phones are not as sensitive as those in dedicated devices. This means all things that affect the ability to get a GPS lock such as tree cover, high buildings etc are much worse. My experience with my e52, is that initial acquisition of the GPS is highly sensitive to having a "clear sky" but once the signal is acquired, it handles building and trees etc pretty well.
Finally, the length of time required to get a GPS lock will vary considerably depending on when you last acquired a lock, where that was, and the strength of signal being received. You will acquire a lock fastest if you recently had a GPS signal and try to acquire a signal in approximately the same location. GPS works by using an almanac of the GPS satellite constellation, which basically tells a GPS device where the satellites are. The GPS signal transmitted from a satellite is time stamped, and the length of time it takes from transmission to reception can be determined, which can be converted into a distance. As the almanac states where the satellite is, by acquired the distance from 4 satellites you can triangulate your position (3 satellite required to for position, the 4th is synchronise times).
GPS takes longer when you try to acquire a new lock a significant distance from where you previously had a lock, if the almanac is out of date, or if you are moving. There are terms for all these (cold start, warm start, hot start) but its been a while and I can't recall the exact definitions and don't want to give dodgy info. The Assisted part in A-GPS uses additional info over GPRS (I think!) to aid in gaining a lock faster. I can't recall of the top of my head the mechanism, but I believe that it provides a coarse estimate of your position which means it much easier get a GPS lock, as the geometry becomes easier to solve if you know where the satellites are and roughly where you are (as opposed to not knowing where the satellite are due to old almanac and having no info on where you are, so you could be anywhere on the earth).
If you've not been able to get GPS signal for a long time, then there is a good chance the almanac is out of date. This automatically updates when you start trying to acquire GPS signal as its transmitted by all the GPS satellites. So to give your phone the best chance of getting a signal:
1. Make sure you have a clear line of sight, away from building, trees, not indoors or in a car.
2. Also make sure you have a good phone signal, as this will allow the assisted GPS to gain a lock faster
3. Place the phone down to ensure your hand is not covering the GPS receiver.
4. Wait. If the almanac is old, then a new one will need to be downloaded and this takes a bit of time.
If you still can't get a GPS lock, then I'm out of suggestion and would start to think there may be issues somewhere else either with hardware, or firmware.
Hopefully you might find some of this helpful.
