When are you trying to go???
Not around the Olympics in SYD I hope.
Have you asked them to check availablity on several days... ask them which days DO have seat availablity to AKL. I was able to book QF Business Class flights last July using US Airways miles and there did seem to be plenty of availability, both in Biz and First. July is the off season so that surely helped. Good luck and let us know what you find...