Welcome Deep Blue.
I think what happend was most unfortunate and could have been handled better both on the phone and at the gate. However, the pax has a resposnsibilty to know the upgarde rules as well as the agent. Your end of the bargain is to know what class of fare you purchased and what type of certificate is required for the upgrade. While the confusion on the phone is not to be excused, you have to admit that you should know what you can and can't do with the certificates.
That is why so many of us want to know what will appear on next year's certs so we can plan accordingly. AC does not seem to understand our need to know well in advance. It affects what we buy now for travel in four or five months.
Back to your treatment. I have personnaly witnessed pax trying to argue that they brought the wrong type of certificate or forgot them, etc. I don't have much sympathy I am afraid. Once faced with the unavailable 'backgrade' I would have insisted to escalate at the counter before agreeing to purchase 'up' in economy. But that is hindsight.
The voucher offer you have, while not great, is a gesture of goodwill that I would consider goes half way to compensate you. I am sure Ac sees it as a half way gesture given that I feel you bear some responsibility in knowing what fare is upgradeable with what type of certificate. The resulting fare shortage situation is neither their fault or yours- they proceeded to sell another cheaper seat on the basis that you had the proper certificate.
Probably not the suppport you were looking for but my honest opinion.