I just noticed that the "free" Navigon app for Australia/NZ popped up again as available for my Galaxy Note, so I installed it from the market.

The market version isn't the latest version, but it's still better (IMO) than Google-Nav. See if it's available for you if you want to get it.

Now, if you want the new version (v4.1), it's only "officially" available to the Australians, which I'm sure is just an oversight. So, if you'd like the latest one rather than the slightly older market version, you need to do the following.

Download and install Market Enabler from: http://code.google.com/p/market-enabler/downloads/detail?name=MarketEnabler_v3113.apk

Open it, find the entry for Telstra (AU), long-press on it and tell it to set it.

Go into the phone settings, then into Applications, locate the Samsung Apps entry, select it and then select "Clear data".

Now run the Samsung Apps application, and once you're in, you should be able to search for "Navigon" and download the current version.

If you reboot the phone, it'll revert back to thinking it's an NZ phone again and all will be well. You can also uninstall the Market Enabler app (all it does is set the MCC/MNC locale codes that the phone would usually read from the SIM artificially)

Some Samsung units will come with the app installed by default, some won't. I like it.