I just had this same thing happen on a B class fare - which I guarenteed to 1st class - and was told an air marshall took my seat at the last minute. I paid extra for b class just so I could upgrade at purchase (3 months earlier) - a cheaper ticket was available. As it was one leg of a 4 leg trip no compensation was offered. I finally - after much time, effort, and 2 bad consumer relation experiences prior to a satisfactory one - was able to change my flight times to a time with 1st available. I was taking a friend on a trip of a lifetime - and 1st class was important to the expeience - hence the extra expense.
There should be some accomadation when guaranteed 1st class is taken away at the last minute and extra $ actually changed hands for the seat. At least a future upgrade or easy ability to change to another time on the same day if it is available (that was my solution - but only after being told no twice).