The current air service rights agreement with Colombia dates back to 1956 and has only been amended three times (1968, 2000, 2002). It still contains capacity controls, so adding a flight is not that simple, especially compared to Latin American countries that have signed open skies agreements like Chile, Uruguay, Peru, and most of Central America, for example.
It has been said - whether wrongly or rightly - that the main reason why AA maintains a flight attendant base in Bogotá was to get on good footing with the Colombian transportation ministry ("Look how many Colombian jobs we have created") so that its large number of Colombian flights would not be seen as violating capacity controls.