I am seeing the same thing and I've read that it's a recurring issue in galaxy phones. My evo was great. Sitting indoors right next to my gfs OG incredible, this phone takes at least 5 minutes to barely locate 2 satilites, while hers locks onto 5+ in seconds. Very frustrating.
Ill try this GPS Fix app... If I'm understanding the description right though I don't much see the point. So it keeps the receiver turned on in the background? If the thing plain isn't seeing satilites, how does it matter how long the receiver is active? I could just as easily leave the maps or navigation app in the foreground and wait just as long for a lock. I guess this would just allow me to do other things while I'm waiting.