While it's necessary to rebook prior to flight time, it is necessary to let them know you're not to fly at least 60 minutes in advance. If you fail to do this, things can get really ugly (e.g. hours on the phone with your TA and the airline, each trying to pass the buck to the other). I usually fare about as well as you did, but I have completely struck out --that is, reached my breaking point and gave up-- in two instances.

Some general advice to anyone else who finds themself in a similar situation (even if you're not in violation of a rule): try to put as much pressure on the TA as possible by reminding you that they represent you (in fact, there is little you can do to advance your cause on your own). Most travel agents around here are loath to go to bat against the airlines because doing so wastes oodles of time. But, when threatened with credit card disputes (I only play this card on rare occasion), they tend to change their tune in a hurry.