The agents are technically right. You can't change your outbound ticket and just pay the fee. Changing the outbound flight means that you have to start from scratch and reprice a new itinerary plus pay any fees--including change and fare differences.
What you need to tell the agent is that you need to cancel this ticket and apply the remaining value to a new ticket. You can't just change the first leg, keep everything else the same and pay the change fee. The ticket needs to be completely cancelled and repriced if you are changing your outbound flight. This could result in a greater price if the fare class for the lowest fare is no longer available or the fare or taxes have since increased (which they most likely have).
You should price out your new itinerary and see what the difference would be and see if it is worth it to you to get a new ticket.