Major Update!!!! Navigon has just released a US version with Navteq maps. $39 for the next two weeks, then $59. I'll be purchasing tonight and will review (although I am biking/Metro to work tomorrow, so no chance to drive with it until Friday at least) but it looks really good, and it is Navteq maps!!!!!!
Navigon's MobileNavigator comes to US Android devices -- Engadget Mobile