I had problems with GPS with my new HTC Desire (Froyo out of the box). I downloaded the "GPS Status" and "GPS Test" apps which showed only two satellites but were not locking them. Even Google Maps didn't get a GPS lock. I went outside of my room and tried but no luck. I switched off the cell, removed the battery, SD card and SIM and then put them back and restarted but still no luck.
Then I installed GPS Essentials from the Android Market. I launched the application and changed the following settings:
- Gps update interval -> 10 seconds
- Tracking update interval -> 10 seconds
After this I tapped on "satellites" on the main screen while standing outside. It detected 8 satellites in a few seconds and it was able to lock to 7 of them. After that everything started working including "GPS Status", "GPS Test" and Google Maps (even inside my room).