In reading your post, I can see two possible interpretations of your issue.
1) Your time-zone is incorrectly set. In this, you can go to Settings > General > Date & Time > Time Zone, then type in your city (or closest major city in your time zone).
2) You're pressing the "Locate Me" icon in the Maps application (or another app is requesting your location). If this is the issue and you're on the original iPhone, I suspect that you're being located by your WiFi access point which was previously geocoded by SkyHook in another city, and it has been moved to another city. Try updating SkyHooks records directly here:
http://skyhookwireless.com/howitworks/submit_ap.php or, turn off your WiFi then try to "Locate Me" again and see if you get different results. If it fails (keeps trying, but never produces a location, then see this thread:
http://discussions.apple.com/thread.jspa?threadID=1596432&tstart=0)
I hope this helps!