If you make a change using a round-trip fare prior to travel commencing, your entire trip will be re-priced as if you are ticketing now -- not based on the date you bought your original ticket.
Non-refundable fares require ticketing within 24 hours of booking (in most cases). If your outbound is no longer available, the invetory you hold won't qualify for being reticketed (as you aren't ticketing this ticket within 24 hours of the booking being made).
If the agent could "rebook" the outbound, this problem would be solved (assuming you still meet the advance purchase requirement). However, since the flight is sold out you would have to select a different flight for the outbound too.
Only solution is wait until you commence travel unless you are willing to chagne outbound flights and likely pay a higher fare in both directions.