the shipping state should be a 2 letter state abbreviation.
can you send the page that has the Australia post behavior applied to it so i can see how it is configured.
If you are passing in the shipping country to the behavior, the zip should not be a problem, it sounds to me like the country is hard coded to Australia, but i cant tell without looking at the code.