<insert airline> vacations are, in my experience, always some travel agency that an airline 'partners' with.

It sounds like you were misled a bit... but keep in mind anything that sounds too good to be true probably is. Paying the change fee penalty plus fare difference when using a 'canceled' ticket is pretty standard procedure for all discount airline tickets. I was actually expecting to read that you weren't refunded the car and hotel cost, too.