These steps were adapted from suggestions on the apple.com support forums and I take no credit for them. These steps were cobbled together for what worked for me.
1. Turn off 3G & WiFi
2. Make sure “Location Services” in General settings is ON.
3. Power down your phone
4. Go outside (GPS needs to ‘see’ the satellite)
5. Power back up
6. Go into Maps and click the locate button (Should happen pretty quick)
7. Turn ON 3G & WiFi (if you’re using WiFi)
Worked like a charm for me.