I feel your pain.

Had more or less the same problem last year for a planned flight YYC to Australia February 1, 2012 and back for February 19, 2012. Thought I would share with you the way that I resolved it.

Was very dilligent about trying Aeroplan starting 50wks from the return date and could find nothing in Business Class for the routing desired (YYC-YVR-AKL-ADL and BNE-AKL-YVR-YYC).

Researching the issue across the web I came across threads saying that the * Alliance partners were limiting release of Business class reward seats to assess market demand in the months leading up to departure and then only releasing inventory into weak demand segments. I continued to be frustrated from my initial attempts in February 2011 upto the new year in 2012.

I had firm dates that I needed to travel as we were trying to coordinate work schedules for myself and my wife and to meet up with friends who live down under. To protect our dates I ended up buying discount Business class seats for ~$7500 each to assure myself of the routing and timing that I wanted.

I should mention we specifically targeted travel outbound on Wednesday to avoid the Friday/Saturday/Sunday crush, and a return on Sunday to avoid the return from holiday's Friday/Saturday traffic.

In early January 2012 I was checking my Aeroplan trapline and came across business availabilities outbound ex YVR through Shanghai or Beijing via Singapore to Adelaide or direct China to Sydney with Air China AND the ability to confirm return to Canada ex Brisbane using ANZ to fly BNE-AKL-YVR. While not overjoyed about the Air China option for the outbound I gritted my teeth and decided to try it for the experience.

When my online booking hung mid processing I called in to the Aeroplan call center for help. A very helpful agent was able to resurrect my booking request and suggested he might be able to do better than the online search engine could.

Ultimately he was able to find one seat in fully confirmed Business Class ex YVR to Australia, but it was an honest to goodness "milk run" and required me to travel five days earlier than my wife (who remained on the paid itinerary). Since I had the extra vacation time available to me I jumped at it.

The routing sequence was YVR-ICN on AC 63, seven hour layover in ICN connecting to a SQ operated red eye to SIN (five hours), a seventeen hour layover in SIN connecting to the once daily service on SQ from SIN to Adelaide (red eye 7hrs) (my desired initial arrival point in Australia).

I remained in Australia for three weeks and was able to open jaw back out of Brisbane through AKL to YVR on the suggested connection using ANZ.

At the end of the day my trip cost me $1500, which alongside the $7500 paid for a confirmed seat seemed like a deal.

The compromises were:

1) A $300 burn to cancel the paid ANZ ticket bought in February 2011 to back stop my trip;
2) Since my reward ticket was ex YVR I needed to buy tickets from YYC-YVR-YYC which cost me $600 - this was a $99 Y class seat sale fare upgraded to J by paying $150 at checkin and a discounted J fare for YVR to YYC so I could sit with my wife on the way home;
3) Fuel surcharges for AC63 of $350 plus airport fees included in the total ticket price totalled about $550;
4) The connecting flight from ICN to SIN was not the first available SQ flight. With an arrival in ICN at 1600hrs local I could have made next SQ flight for SIN at 1900, but no confirmed reward seats nor airport standby was available. The flight did have space, I just would have had to pay to sit in it;
5) I was underwhelmed by the asia regional service on SQ's A330 after hearing all the buzz about how attentive the service was. The SQ seats were 170degree pitch seats (similar layout to Lufthansa business class) and so adiquate for sleeping, but not fully lie flat. It is debatable whether it is a fair comparison or not, AC installed lie flat for thier long haul flights and SQ's A330s are plying medium length regional routes more akin to North American transcon - should one expect the same level of amenities? At any rate, for a guy simply wanting to sleep on both SQ red eyes the AC lie flat is better IMO.
6) The ANZ Business Class lounge in Brisbane is small and pretty plain jane. The flagship ANZ lounge in AKL is nothing to write home about either and is very very busy in the late afternoon as all the trans Pacific flights prepare to depart at the same time. Truely you wil spend more time in the shopping area around the gates than sitting in the lounges.

The pluses were:

1) $6000 saved off the paid fare;
2) The opportunity to spend an extended time exploreing both ICN and SIN airports (if you've never been both are worth the experience as they are ranked in the top five world wide);
3) I had sufficient time to spend ten hours in the centre of SIN itself, which whetted my appetite for a return visit with wife in tow.
4) I got to experience the Asiana Business Lounge in ICN and the Singapore Business Class lounge in SIN. Taking some sweats to sleep in on the plane, plus a shower and shave on arrival in both cities did wonders to help me kick jetlag.

In sum, my advice would be to book a cancellable "plan B" if you really want to make the trip on a specific time line and to keep checking especially once we get into the new year.

Additional feedback...

I asked the in charge on our ANZ flight back from AKL to YVR about load factors for that route given the difficulty I had booking the rewards seats in the first place. His comment was that he was seeing flights out of North America leaving near 100%, but that flights outbound from New Zealand to North America were relatively lighter. This was during Rugby World Cup in Janaury/February 2012 - so perhaps additional tourist pressure (???) due to the event, and this year (2013) might be slightly different. Given that Australia is a relatively sun oriented destination for those trying to escape Canadian winter in January and February - this is likely an annual issue and is, therefore, unavoidable. Your mileage may vary.

One more factor to consider is that YVR-AKL-YVR is operated on ANZ's 777-200ER (corrected thanks to Clouds Below's post which follows) which has lie flat seating but not the newest Business Class interiors installed in the fleet of 777-300ERs which began arriving 18-24 months ago. I was told that there are small differences in the seats themselves - primarily that the 300ERs are equipped with a memory foam topper mattress which is rolled out by the FA when the seats are deployed prior to sleeping (you need FA assistance since you cannot actually be seated when the back of the seat flips over to form the lie flat portion). On the 200ER return, we got the matress toppers, but they didn't seem to fit the seats on the 200ER as well as they should have. (I further recall the in charge saying that the seats were obtained under license from Virgin Atlantic - so if you are familiar with what they are using then ANZ has the same set up.)

If you want the 300ERs you need to travel ex LAX or SFO (which might be easier from a rewards perspective) and you DO run the risk of a last minute substitution with a B747. In fact traveling to SFO three or four times in the spring and summer of 2012 I can't recall seeing any thing other than the 747 at ANZ's gate.

Good luck.