When you change the dates on a ticket before you begin travel, at least officially, you are basically buying a new ticket. If your original ticket was nonrefundable/had a change fee, then you are charged whatever the fee is, and the value of your old ticket is applied towards the cost of the new ticket. Note you can use the value of the old ticket to fly to a new destination, in esence, it becomes like a credit on the particular airline.

So again in theory if I had a ticket BOS-LAX for Tuesday 1/9, and I needed to fly Wednesday 1/10, I would need to pay the full fare because I would probably not have enough advance purchase to quallify for a discounted ticket.

That being said, most often at the airport itself, exceptions can be and are made. They might change it for you for free, or perhaps charge you the $75/$150 only, when they really should have charged you difference in fare as well.

Now I have no idea about the fares in this market you are writing about, but if you got some incorrect fare, they will perhaps be less likely to change it for you in this unofficial way.

I would recommend that you go in person to the airport or city ticket office, and see what you can do. Also if you called the airlines reservation department, they probably documented your record saying you were advised that you would need to pay adcollect plus change fee. If you made the inquiry through Travelocity itself, then there is a better chance that this travel agent did not document your airline record, so you would still have an outside chance of having somebody work with you at the airport. In a best case situation, an airport could simply "sticker your ticket," placing a revalidation sticker with the new flight/date on it without doing a reissue. Again whether they do this is a matter of pure luck, who you talk to at the airport, if they like you personally, if they are in a good mood, etc. Being a frequent flyer also doesn't hurt. If its the difference between $5,000 and $3 or $400, it's probably worth a ride out to the airport to try your luck.