dial this from your phone:
*#*#1472365#*#*
Change startup from hot to cold.....worked for me. GPS locks much much faster
I'm having the same problem here. My iPhone 3GS GPS responded way quicker then this phone does. I have a Weather Channel widget up, and it doesn't find the location to display the weather for a good minute and a half after. Same goes for using Google Maps to find my location. Lot of times it says, "Your location is unavailable." I even tried switching the startup from hot to cold, and that didn't have much effect either.
When I was driving today, the GPS locator had a bad lag in it, I would be down two blocks before it would catch up, and I live in a 3G area, and not a giant city like NY or something.
I wonder if it's because it's so bloated with Samsung UI on it, or if it's just the a bug. Either way, if I'm still having issues with it, I'll see if AT&T will exchange it out for a different one. Otherwise back to the 3GS, which I really don't want to do since I'm loving Android right now.