I knew there would be some growing pains with Google Navigation. in fact, Google Maps too recently changed from purchasing their road data from Navteq and TeleAtlas to using their own data and using the US Census Tiger Database to fill in gaps.
Areas where the street view van has been are well mapped, but areas where it hasn't been may have soem issue because the Tiger database is not nearly as good as Navteq or TeleAtlas.
However, I strongly suspect that Google Navigation is collecting data to feed corrections to the Google maps team (the team also responds very quickly if you report an error, and since the maps are in the network, everyone instantly benefits). I think every time Google Navigation is forced to recalculate because you don't follow its directions it sets a flag to have someone review the data.
All well and good, and I think I have seen this in action. I have been using Navigation almost everywhere I go, even when I know where I am going, just to play with it. Near me, there is a lot of road construction going on, and the first time I came to a certain intersection, GN told me to take a temporary ramp that has been gone for about six months. (My Garmin with 2009 maps makes the same error, with 2008 maps, it is even worse since they replaced a lighted intersection with a ramp and overpass). Three days later, on the same route, I got the correct instructions.
The strange thing is what happened night before last. I went to a restaurant I have been to before. My Garmin GPS always had me go past the restaurant, make a U-turn to cross a divided road, and then come back to turn right into the parking lot. The thing is, there is a left turn light at exactly the place it has me come back to, and it has been there for many years, so there is no need to go to the next intersection and make a U-turn.
Google Maps used to make the same error when it got its data from Navteq (same source as Garmin).
A few weeks ago, using GN, It knew about the left turn, correctly navigated me to the restaurant, and even had a street view image at the end.
Two nights ago, it had me make the U-turn, and didn't end with Street View showing me the restaurant. maps.google.com makes the same error (as I would expect, since it should be using the same data).
Similarly, on the way home, a few weeks ago, it correctly took me off the highway at my exit, which goes to a service road for about a mile before the turn towards home. This exit has been in place for about 18 months.
Two nights ago, it had me pass the exit, take the ramp into a commuter parking lot, which I can cross into a service road behind a shopping center and get to the road home. This would have worked, but is much slower having several stop signs, and a much slower speed limit.
Since in both cases I went the correct way, rather than following GN, I am looking forward to seeing if the directions get updated based on my reroutes when I go this way again in a couple of weeks.
Lesson though, don't rely on Google Navigation 100% in unfamiliar areas. If you have access to another GPS or even (god forbid) paper maps, you may want to bring them along in case GN gets you hopelessly lost.