I'll try to help but your question has it probably been answered a dozen times in the past year on both the UA and AA boards. Try a search on those boards also...

As you may know, AA just came out with a new award chart which makes it more difficult to fly to Australia from the USA since flying CX is no longer an option for the direct awards.

see: http://www.aa.com/content/AAdvantage..._chart.jhtml#1

Note that it will cost a minimum of 75K miles to get there with AA miles.

BA came out last year with a new chart and it has also gotten more expensive, especially in the premium cabins.

UA thankfully still has its own as well as the Star Alliance charts (60K in coach). You will probably find it most cost effective to fly UA and the Star Alliance given the (1) availability and (2) the lower redemption levels. Note that the only airline that now flies direct to AKL from the States is NZ.

Awards to Australia are never easy to come by. You have to be very diligent and call everyday if necessary...