Dear brj,
I know how frustrating it can be when an airline abruptly cancels a flight that is an integral part of a carefully crafted trip. It happened to us on a trip in India in December; the day before we were to leave, a flight was rescheduled by several hours, creating a misconnect with an onward SQ flight. Neither the airline nor the travel agent informed us. I'll spare you the war stories on the problems it caused us when we found out in India!
I am unsure as to your question about "rights"; I don't believe that you have any, as airlines have the right to modify their schedules for THEIR convenience, not yours.
Having said that, have you spoken to your travel agent about alternative flights? I looked at my OAG pocket flight guide for Asia. I don't see any AA flights into Osaka or Tokyo that have onward connections to Denpasar. However, if you fly AA to SFO, you can pick up a CX flight to HKG, which has an onward connection to Denpasar.
AA753 DFW - SFO
CX873 SFO - HKG
CX785 HKG - DPS
And of course, there are connections thru LA and SFO on SQ via Singapore to Denpasar.
Enjoy your travels!