For a vacation in May, 2004, I started trying in July of 2003. I was unable to get LAX-SYD on the outbound, so I accepted LAX-AKL-SYD. I called 28, 21, and 14 days before the trip. The LAX-SYD nonstop opened up, so I paid $50 to change the itinerary.

IMHO, I should have received the nonstop to begin with but at that point it was worth $50 each to avoid the layover.