A lot of GPS only devices take a long time to locate depending on the circumstances (did you just turn it on after a long time of being off or after a complete battery drain or if you had it on in one location but turned it on again in a location a very long way away like hundreds of miles...)
Since the phone is a phone with a GPS rather than a dedicated GPS, I can see it taking some time to perform this task. However, I have never seen my Droid X take longer than a couple of minutes to lock and locate and it's always receiving 10 or 11 of the full 12 satellites it can track. It's very impressive. It also receives inside fairly well unless it's a multi-story building or one with lots of cement and rebar.
This past weekend, I turned the GPS on inside the house, went to the Navigation app, punched in the address to where I was headed, walked out to the car, put the phone in the cup holder, started driving and it immediately told me the directions. Fast enough for me.
So mine works pretty darned fast.