Hertz and many car rental companies are franchises here in the US. This means that not all will implement corporate policy equally. Additionally, they are VERY short on the terms regarding licenses. See here:
An acceptable, valid driver's license issued from your country of residence must be presented at the time of rental. The driver's license must be valid for the entire rental period. If the driver's license is in a language other than English, and the rental is in the United States, an International Driver's Permit is recommended. In all cases, a valid driver's license issued from your home country must be provided, whether or not you possess an International Driver's Permit. You will not be allowed to rent a Hertz vehicle with only an International Driver's Permit.
Your license is obviously in english if from AUS, so don't worry about IDP for renting a car, whether it's needed to actually drive I'm not sure.
I would recommend you contact other rental companies until you find one that is happy to accept your business!