I tested the Navigation app today for about 15 minutes. It found my location instantly, looked up my destination in about 20 seconds on 3g, and gave me step by step voice instructions all the way to the destination, and popped up the street view of the destination about 100 yards before I arrived there.
After reading a pastebin from someone who said navigation was crashing, I noticed that particualr person had no network access just before the usage. This leads me to believe that issues with navigation are related to network connectivity at the time you are attempting to use it.