See género en ciudades y países from Fundéu:
5. Cuando se antepone todo, el género alterna en todos los nombres de ciudades: todo Bogotá o toda Bogotá. En España y México, se emplea el giro el todo, siempre masculino, para referirse a la élite social: el todo Barcelona.
and ¿Es toda Europa o todo Europa? from Castellano Actual:
Finalmente, cuando los topónimos acabados en -a se combinan con el cuantificador todo, admiten tanto la concordancia femenina como la masculina (todo/toda Europa; todo/toda Venezuela); aunque se prefiere el femenino.
Though Colombia is a feminine noun, when the word todo comes before a country or city, both todo and toda are acceptable.
In Spain, I hear toda España much more often than todo España. (I also have never heard that construction el todo Barcelona).