This is most likely a mistake that will be fixed at some stage. So far this has only worked for Android 2.2 flashed Galaxy S phones.
If you have another model or haven't flashed your Galaxy S, don't bother reading further.
As listed in Whirlpool here, http://forums.whirlpool.net.au/forum-replies.cfm?t=1573664
My Galaxy is running Doc Kalpik 7.6.2 JPO firmware ( available here: http://forum.xda-developers.com/showthread.php?t=817703) which is surprisingly painless to install and running great!
The Navigon App appears in the Market as a Free App, I think this a bug in the Market probably because the Samsung Galaxy Tab (which officially has Navigon as a Free App in Australia) is so similar to the Galaxy S and is the only Samsung device currently (officially) running 2.2 in Australia.
It doesn't appear free in Appbrain, nor does it seem to work for Non-Samsung phones.
Not bad, especially if Optus gives us Froyo on Monday.