I don't see why the date / routing is relevant? flight is booked from JFK-HND stopover, HND-CTS in J. i'm trying to change to a different HND-CTS flight on the same day also in J. the flight shows up when searching HND-CTS on AS/QF/BA/AA , as well as when i search JFK-HND stopover, HND-CTS, so it's definitely not a married segment issue.
I'm 99% sure it's an issue with the phone agent's system. In the past, I've successfully booked many flights on the website that agents were unable to see (multiple phone calls, so not an one off issue). If they didn't break the change flight tool, i wouldn't even have bothered calling. Again, 99% sure that the old change flight tool would've just worked ...
The routing and dates would allow me to check availability independently in case there was some situation that wasn't mentioned in your vague description which caused a problem. What you have provided I think is enough to get a handle on it. With your JFK-HND, stopover, HND-CTS routing there should be no issue in changing to a different HND-CTS flight on the same day so long as it shows separate availability as you say. My guess is you are just running into poorly trained agents of which AS has many. Make sure to call the partner number during business hours. If they have trouble after you point them to their own website which shows availability and you also point out other partners are also showing availability and talking to a supervisor does not help, here is a technique I once used to prove to the agent that the availability is live and not phantom (requires extra miles in your account):
1) While the agent is on the line tell them you will book the HND-CTS flight you want separately to show that there is availability (best done if there is 2x the availability you need showing).
2) Book the new HND-CTS flight online separately and it should book and complete.
3) Point the agent to your new booking showing them the availability really is live and so they should be able to use it for your existing reservation.
When I have done this it proves to the agent beyond a shadow of a doubt that they were wrong about the availability and something is wrong on their side. They get a supervisor involved to sort it out, change the flight, cancel the useless booking used for proof, all ends well. It can be done but in some cases they will not do it because they believe it cannot be done and you have to prove to them that it can so that they are forced to spend the time to figure it out.