Air NZ is still nominally a member of Star Alliance, but the airline doesn't comply with the idea of offering award seats on its popular routes. NZ hasn't offered an award seat in C on any of their direct US flights for more than a year. There's very infrequently a seat out of YVR, or on the island-hopper from LAX.

UA's two services to SYD from LAX and SFO have been so plagued with mech failures and overcrowded rescheduled planes that UA has also reduced or stopped offering C awards. Next year they will finally change the aircraft on this route but that will reduce size of the C cabin, also bad for awards.

The "easiest" C award route from the US to Australia is Asiana via Seoul. They have flights from ORD, JFK, LAX, SFO, and even SEA. SQ via Singapore sometimes works too. If not try some convoluted routings via BKK to get that final BKK-Australia sector which is usually available in C or even F. In fact TG F from SYD to London is often available if you want to go the long way round. And London-SYD but then you're up for swingeing UKAPD taxes.

There are options via Japan if you're prepared to pay some of the way, the Jetstar flight from OOL to NRT is very acceptable in "Star" class especially if you get the front row, and is often on special $500- $800 each way. Edit - Here in OOL it's a great place to visit, and there's an NZ connection (Y only) 3 times a week with some Y awards.

If you can only get as far as SIN, the Y fare from SIN to PER is around $250 and it's do-able in Y, 4.5 hours. There's an NZ flight PER-AKL which used to be easy for awards but on the NZ board they're complaining that awards just dried up there too. SIN-BNE on Etihad is another alternative, Etihad Y is bearable at $380 and ther's award space BNE-AKL