A lot has been said about the iPhone’s ability to locate the user; the new 3G iPhone actually uses GPS to do this, while the original iPhone just uses triangulation from cell-phone towers to figure out where you are.
The triangulation method should work reasonably well for most purposes (i.e. ‘what town am I in?’ at the very least), but my experience lately has been that this isn’t the case.
The other day, I hit the Locate button and got this result. Click on the picture for a bigger version:

Where I was standing, the terrain is such that there’s no signal at all from the south and west. Where I was standing, the elevation is 700 feet, and the mountains are about 2300 feet. You can see the problem (if you squint) in this view looking roughly south. Click for a bigger version:

There’s also a low ridge between the airport (where I was standing) and the town of Front Royal itself. It’s not enough to really notice, but it’s enough to block cell phone signals. My guess is that the phone could get only one signal, and that this was from a cell site on or near Mouth Weather, which is just NE of the identified (wrong) location. All the system could tell was that I was somewhere on a line roughly 210 degrees from that tower.
The lesson: cell-phone triangulation location information can be ridiculously inaccurate when in areas with interesting terrain and poor coverage. More importantly and less obviously, the locator system appears to be unable to reliably determine when this is the case.

Comments
Here in DC CoreLocation is disturbingly accurate (like down to 100 meters or so), but that seems to be solely based on the availability of WiFi signals. Wherever I try it here — assuming I give it long enough to work — it comes up with a radius of uncertainty of about half a DC block, but with the center of that circle invariably no more than 10-15 meters from my actual location.
Maybe I’m trying it in particularly WiFi-dense neighborhoods, but still.
This doesn’t address the bug that CoreLocation sometimes gives you either stale or incorrect data and then stops locating, instead of refining the location like it’s documented as doing. I would guess out in the sticks you’re running into both weak signal for triangulation and the apparent early-give-up bug.
I do get stale data, of course. But that’s usually easily detectable by just getting the Maps app to locate you again. In this case, it’s telling me that I am definitely within a circle with a radius of a mile, centered on a point 15 miles away. It will tell me this repeatedly.
It would be far better if it would just say ‘you are somewhere in this 30-mile circle’; at least then I’d know it was useless data.
why would having a lot of WiFi around help with finding your location?
I used to fool around with my Sprint phone. a few key presses and I got into diagnostics which gave me a 2 hex digit signal strength meter and the number of the transceiver (there were usually three or four transceiver per pole). You could kinda-sorta get a direction fix if you did things like shield the phone with your body and look at the signal strength meter.
While I was fooling around with this, I was envious of the (I think) GMS phones. If I remember correctly, the tower also gave out it’s “missile address”, which you could read when the phone was in diagnostics. I also seem to remember that there was a limited distance that packets could be passed to the tower. Over a certain amount of time, the packets are dropped. If you know the round trip time and the location of three towers, that should be everything you need to get a fix, although I’m going to guess that there are no caesium clocks in cell sites.
Regardless of how the locating is accomplished, even my 1997 era GPS let you know how accurate the fix was.
Ah, the Google incantation seems to be: “Time difference of arrival”|TDOA iphone
The wifi helps because of Apple’s business relationship with Skyhook Wireless, who do wifi-based location. As with GPS and cell tower triangulation, the more data points you have the more accurate your location fix will be.
Ah, the Skyhook link was pretty interesting. Wardriving pays off, maybe. I assume that they would need to drive around the city streets every once in a while to freshen their data. I’d love to have a peek into the equipment that they use.