I'm getting very interested in GPS problems across the entire iOS device range. Ive got a 3GS and the GPS satellite fix stopped working completely recently. A fix identified using jailbreak and an ssh terminal tells me a good proportion of these problems are with locationd, the gps process in the iPhone, or more accurately, I think that it's possible for some of the data this process uses to become corrupted; the "fix" involves stopping the process and deleting the data it uses. On restart, locations is forced to rebuild the data, and everything then works.
I suspect this is true across the iPhone range - and worse, I think that the backup function in iTunes actually backs up the bad data. Thus, when you restore from backup, you actually put the problem back in! Either that, or GPS cache data isnt deleted when the iphone is restored.
What we need is an option in iTunes, or the iPhone settings, to clear GPS ephemeris and related data down and restart locationd: this will save apple a fortune in support at genius bars, as I reckon everyone who is getting a replacement is just getting a reblanked refurbished iPhone with no hardware fixes - they could be turning them around in the back of the stores!
We need to get some group pressure together to get an answer out of apple on this really - they do seem to have an approach which has much in common with the way the UK banks were dealing with overdraft fees - if you complained, they refunded just to keep you quiet and make sure you didn't shout. If this issue is an underlying gps driver or application demon issue, they should give us a way to work around the issue.