Thanks for all the suggestions. I have worked before with Elliott Advocacy, even if not for airlines matters, and they are very nice. What worked for me in previous disputes with airlines, in a couple of situations that were even nastier was sending a complaint through the DOT. After the back and forth with the airlines (BA in one case, Iberia in the other) had gone on for months with repeated denials, the complaints to DOT resolved both situation to my complete satisfaction.

For anyone interested, below is the draft of the complaint that I am planning to send to Avianca.

Before I explain my complaint, let me start by asking four questions, whose answers provide the keys of my complaint
Question 1: is Avianca responsible for keeping up to date with the latest rules on the travel requirements to fly to Colombia?
Question 2: is Avianca aware of the statement about vaccination requirements shown on the webpage of the Ministerio de Comercio Industria y Turismo de Colombia?
Question 3: If Avianca fails to follow the latest rules and wrongly denies boarding to a passenger, who is responsible for the related monetary damage, Avianca or the passenger?
Question 4: If Avianca fails to follow the latest rules and wrongly denies boarding to a passenger, does Avianca feel entitled to ask the passenger to pay extra money for a replacement ticket?

Here are the facts of my complaint: on April 11 I was denied boarding my flight from Sao Paulo to Bogota because the Avianca agent at Guarulhos airport told me that all passengers flying from Brazil to Colombia are required to show a yellow fever vaccination card, and that this is a "well-known longstanding requirement". The Avianca agent's claim forced me to miss my flight, despite the fact that I had succesfully completed the online check-in process the night before and that the travel requirements that the Avianca website had disclosed to me stated that yellow fever vaccination card is needed only for "Passengers visiting high-risk zones for yellow fever", whose list did not included any of my stated destinations (Bogota and Medellin) https://ayuda.avianca.com/hc/en-us/a...udes-COVID-19-

After I was denied boarding, I did some research and I discovered the following facts:
1) The website of the Ministerio de Comercio, Industria y Turismo of Colombia https://colombia.travel/es/informaci...alud-y-vacunas says the following "Actualmente, no hay vacunas requeridas para ingresar al país. "
2) The Latam website at https://www.latamairlines.com/br/pt/...gem/restricoes states exactly the same requirements that were stated by the Avianca webpage.

Can you please explain me how is it possible that the Avianca rep in Guarulhos enforces a different and more stringent set of requirements than those specified by Avianca in the webpage above?
In light of these facts, I am claiming that by denying me boarding my flight Avianca failed to abide to the requirements that were in place at the time of my flight and which were all satisfied by the documentation I presented. For this reason, Avianca is responsible for the monetary losses that I sustained as I was forced to cancel my plans. The only remediation that Avianca offered, i.e., rebooking a flight for the same number of LifeMiles and same itinerary was clearly insufficient because I had purchased my flight well in advance for an amount of LifeMiles much smaller that the amount generally required to purchase a flight just one or two days in advance. In fact, no flights satisfying the requirements were available in the next few days. My position was and remains that since Avianca acted wrongfully in denying me to board my flight, it should have indemnified me by the current value of the flight and not the value at the moment in which I bought it. In other words I asked to be given a ticket for the earliest available flight at no cost, independently or whether or not it was available as an award flight. This request would have allowed a quick satisfactory resolution in which I would have accepted to bear parts of the costs caused by your decision. Unfortunately, it fell on deaf ears as i was bounced from customer service rep to customer service rep and none of them claimed to have the authority to do that. As a result, I have been forced to completely cancel my travel plans to Colombia, maximizing my losses of which I consider Avianca to be fully responsible. I can understand the logistical difficulties of handling uncertain situations of requirement changes and the potential errors that can accompany that transition. What I cannot condone is the complete unwillingness to admit that a mistake was made and support my attempts to work towards an acceptable solution that could have allowed me to save part of my travel. A behavior whose only result is to wipe out any potential plan to entrust Avianca with future travel plans. I will soon send a document detailing all the expenses resulting from your wrongful disruption of my travel plans and for which I am requesting full refund.