Did you originally book online or via phone? It's a very different set of agents depending on that. Online bookings deal with Expedia I think. Obviously it costs $39 to book via phone (and for any changes too), but I suspect you would have been more than happy to fork over that money after this experience.