Australia and New Zealand being lumped together for the "wholly within one country" 20,000 mile award does make it a great use of AA miles.

My experience is with the 20,000 miles awards within Australia, and with advance planning it was easy to find availability on the nonstop flights I wanted. A check of the award availability tool at qantas.com, or looking for the "X" bucket at expertflyer.com should reveal a general picture of award availability between Australia and New Zealand.