According to a story in the NBR, Telecom XT will be releasing the Motorola Milestone as of July 1st *INCLUDING* turn-by-turn navigation in Google Maps.
Unless they somehow restrict this is to Milestone, it looks like this functionality may be enabled for all Android phones in NZ from about that date. Fingers crossed.
Turn-by-turn navigation was enabled for Canada and many European countries a week or so ago.
Quoting text extract here for posterity:
"Turn-by-turn navigation instructions
A signature feature of Android 2.0 is a new version of Google Maps with voice-enabled turn-by-turn directions, a feature Telecom confirms will be available with the Milestone's local release (which will run on Android 2.1; a welcome climb on the Xperia's 1.6; the most up-to-date version is 2.2)."
Unless that is a hopelessly lost mash-up of boilerplate from some other source, it's looking good for turn-by-turn nav. (I don't recall if that was not operational on Android v1.6. I've been playing with v2.1 ROMs since late last year.)