Around 100 protesters burned French flags and threw stones at the French embassy in the Bolivian capital of La Paz on Wednesday as they vented their anger over claims France had banned President Evo Morales's plane from entering their air space.
"Hypocrite France! Colonizer France," shouted the protesters, who included representatives from indigenous groups.
"Fascist France, get out of Bolivia!" they chanted.
The protests which were mobilised by groups close to Morales followed accusations by Bolivia's Foreign Minister David Choquehuanca that France and other EUropean countries had cancelled air permits for the plane carrying the president, who was heading home from Moscow, after suspicions were raised that the NSA whistleblower Edward Snowden was hiding on board.
The Bolivian parliament will discuss a motion on Thursday that calls for the the French ambassador as well as the Italian and Portuguese envoys, to be expelled from the country.
"We will seek a declaration that these three ambassadors become persona non grata, out of respect for Bolivians but most of all out of respect for the life of the president," said opposition member Galo Bonifaz.
Morales had been in Moscow, where Snowden is currently holed up out of sight at the city’s airport, for energy talks.
As he began the journey home, suspicions began to spread that the fugitive former CIA operative might have been sneaked on board the plane bound for Latin America, Britain’s Guardian newspaper reports.
Foreign Minister Choquehuanca told reporters that both France and Portugal had subsequently cancelled authorization for the flight to pass through their air space at the last minute.
"They say it was due to technical issues, but after getting explanations from some authorities we found that there appeared to be some unfounded suspicions that Mr. Snowden was on the plane,” he told reporters.
"We don't know who invented this lie. We want to denounce to the international community this injustice with the plane of President Evo Morales," he added.
Choquehuanca said France’s decision had "put at risk the life of the president".
Later on Wednesday French President Francois Hollande said he had opened his country's airspace to the Bolivian presidential jet as soon as he knew head of state Evo Morales was aboard.
"There was conflicting information about the passengers who were on board," Hollande said in Berlin. "When I knew it was the plane of the Bolivian president, I immediately gave permission for it to fly" over French territory.
And Foreign Minister Laurent Fabius moved to quell the row by calling his Bolivian counterpart to "offer an apology" for not granting permission to the president's plane.
Morales’ plane was eventually allowed to refuel in Spain before flying on to Vienna where the plane landed with no sign of Snowden.
Bolivia is one of the countries to which Snowden has officially applied for political asylum. Bolivia’s left-wing president has previously suggested that Snowden’s application would be viewed favourably.
Bolivia’s defence minister Ruben Saavedra later told reporters that France had reconsidered its position and decided to allow the plane to fly through its airspace, but Italy and Spain were still refusing.
Later on Wednesday France said it had given permission for Bolivian President Evo Morales's jet to cross its airspace, after officials in La Paz claimed that overflight had been denied.
"The permission for overflight was indeed given," foreign ministry spokesman Philippe Lalliot said but refused to confirm reports that it had not been initially granted.
The damage however had already been done with angry Bolivian authorities claiming that France had bowed to pressure from the United States in refusing to grant permission to the plane.
Saavedra said: "This is a hostile act by the United States State Department which has used various European governments."
The Bolivian government said it would be demanding explanations from both Paris and Lisbon over the affair. France’s refusal sparked an angry protest outside its embassy in the Bolivian capital La Paz. Bolivian authorities said further protests would he held in the near future outside the US embassy.
Morales's plane is still in Vienna whilst Bolivian officials try to work out their options for how to get the president home.