You cant use the Iphone maps but do a google search for maemo sygic australia and you will find what you need. Its about the 6th result from the top. Applies to NZ aswell, they are in the same mapset.

What I did is download Mobile maps through Ovi store then added the australia map to /opt/sygic/maps/

Its a pitty we have to result to hacked software when the author wont release the required version for us.