Consider buying it in Canada where they a clue. The problem here seems to be that AA handles its NZ sales out of Australia and they can't deal with the fact that an Australian buying a ticket in New Zealand means that the Country of Sale is New Zealand.

Oh, and another little trick that might be worth trying - very few credit card processing companies validate the address of the credit card for addresses outside the USA (in most cases it simply isn't possible except by manual intervention given the non-standard format of addresses). You could try simply giving them a New Zealand address for the card. It would probably work.