Se você está certo de que é um cidadão dual, então precisa de um passaporte colombiano (e também, se a embaixada for acreditada, um cartão de identidade). Da Perguntas frequentes página da Embaixada da Colômbia nos EUA:
If I am traveling to Colombia and I have dual citizenship, must I enter Colombia using my Colombian passport?
Yes. Colombian law requires that all Colombian nationals identify themselves as such by presenting a Colombian national ID card and a Colombian passport when entering the country.
No entanto, se você nasceu antes de 4 de julho de 1991, talvez não seja um cidadão duplo. A Constituição vigente na época proibia a dupla cidadania para os colombianos, segundo a mesma página:
I was born in Colombia, but I have acquired U.S. citizenship. Can I enter Colombia using my U.S. passport?
If you obtained American citizenship before July 4, 1991, under Colombian law you are no longer considered a Colombian national due to the fact that, under the Colombian Constitution of 1886 — which was valid until 1991— holding dual nationality was prohibited. Therefore, you must enter Colombia with your U.S. passport. (In this case, we encourage you carry a copy of your naturalization letter.) Be advised that if you enter Colombia with a U.S. passport you will be subject to Colombian immigration laws.
Please note that those who obtained American citizenship after July 4, 1991 did not lose their Colombian nationality and therefore hold dual nationality.
Mesmo se você nasceu antes de 4 de julho de 1991, no entanto, você pode ser um cidadão duplo. Não consegui encontrar uma tradução em inglês da constituição de 1886, ou mesmo uma cópia eletrônica do texto em espanhol para tradução automática, mas observo as palavras "se você obteve a cidadania americana". Alguns países prevêem a perda automática da nacionalidade de qualquer pessoa que obtenha outra nacionalidade, mas tal disposição muitas vezes não se aplica àqueles que nascem com múltiplas nacionalidades. Esses países também podem ter outras disposições que levem à perda de nacionalidade em um momento posterior (a maioridade, por exemplo, ou algum tempo após a maioridade) ou sob certas condições (dependendo se a pessoa reside no exterior, por exemplo).
Eu não conheço a lei colombiana sobre este assunto, mas se você nasceu antes de 4 de julho de 1991, você pode querer investigar mais para determinar se você ainda é um cidadão colombiano. A maneira mais fácil de determinar isso pode ser perguntar no consulado ou embaixada em conexão com o seu potencial pedido de um novo passaporte.