According to an article in El Colombiano AA wants to operate flights between Miami and Medellin. Right now this isn't possible until at least Oct. 2002 due to the bilateral agreement between the USA and Colombia. At the present time, carriers from the USA only can operate flights to Bogota, Cali, Barranquilla, and Cartagena.
Yesterday Avianca began non stop service between Medellin and JFK 3 times a week (I think for the summer only).
Also Spain and Colombia are negotiating an open skies agreement. Colombia want more Spanish carriers to operate flight to tourist cities such as Cartagena, Santa Marta, and San Andres.