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][1] 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).

  [1]: https://market.android.com/details?id=com.mictale.gpsessentials