It's could be an issue with you being in the wrong store, BUT I thought the NZ and Aus stores were pretty much the same and pretty much compatible. You should be able to find instructions for changing your itunes store from NZ to Aus via google. My iPad is wifi only and I can't verify the procedure on it so I would rather you follow an online tutorial that my remembered instruction, but it involves starting up itunes on the device and changing the flag at the bottom.
EDIT: Alternatively you can go to an Apple Store and they can do it for you.