When I bought the iPhone I noticed that there was an incredible lag when using Location Services. Today I asked the Maps application to find my current location. 20 minutes later it was still thinking.
I called Apple and, after a bit of searching, the tech gave me this solution:
Turn iPhone off and back on. Disable 3G. Disable WiFi. Use Maps to find current location (worked!) Re-enable 3G and wireless.
I power cycled again and my GPS was still working.
24" iMac 2.33 GHz Intel Core 2 Duo, Mac OS X (10.4.10), AT&T, East Coast, United States