Colombian Tourism addresses the issue straight away: "Colombia ... the only risk is wanting to stay". I admire the upfront approach to the country's dodgy reputation but, as I'm surrounded by men holding guns, I'm not entirely sold on the slogan.
Luckily, the military aren't after me today. Instead, they are here to protect my group as we hike through jungle once occupied by the paramilitary. Bored, they are just happy to have new faces to play a game of cards with.
Rifles propped against tables, introductions made, we use our best Spanglish and get down to it. If I were anywhere else, I'd find it a little odd to finish my day playing the children's card game "Uno" with the military. But in Colombia, I've come to accept anything can happen.
Not so long ago, Colombia was one of the world's travelling black holes, a lawless country torn apart by civil war. But with a new government, the country has begun to clean up its act and undergone a major tourism makeover.
While there's no doubt Colombia has a serious safety hangover, its "dangerous" reputation has actually given it street credibility among travellers. Visitor numbers are up as people look for a slice of South America that is edgier, cheaper and more off the beaten track.
Guidebooks in hand, the backpackers are the first to return and they've done it with a touch of old-world style, sailing from Panama to Colombia via the San Blas Islands. The five-day journey avoids the Darien Gap, the extremely dangerous overland route through the lawless terrain between Panama and Colombia, and sails straight into the heart of one of Colombia's tourism hotspots, the Caribbean port of Cartagena.
Cartagena was given UNESCO World Heritage status in 1984 and it's easy to get lost in the jumble of cobbled streets inside the 400-year-old fortress.
Pastel-coloured mansions perch proudly along the avenues, their windows overflowing with summer blossoms. Horse-drawn carriages whip around carrying cashed-up tourists and the plazas are filled with shady, umbrella-strewn cafes and even shadier characters.
Cartagena was once a hive of villainy where pirates laid siege, thieves traded in stolen gold and smugglers ruled the docks. But all this adds to the city's swashbuckling appeal.
The streets burst with energy and I half expect Jack Sparrow to stumble around the corner brandishing a flagon of liquor.
Hot on the heels of the backpackers, cruise ships have arrived in Cartagena, followed closely by Europeans on package deals. The main attraction is Colombia's unspoilt coastline, increasingly punctuated by all-inclusive resorts with heavy security, heaving buffets and open bars.
However, step away from the white beaches and resort towns of the Caribbean Coast and the country begins to shape-shift. There are still a number of "hot" zones where it is unsafe to travel and, while conditions have become more stabilised, it's important to be aware of any deteriorating conditions.
But venturing inland rewards the brave with precious spoils. One of the country's jewels is Ciudad Perdida, or the "Lost City", in Tayrona National Park. Four hours east of Cartagena, the abandoned city was discovered by treasure hunters in the 1970s. For Indiana Jones fans, the six-day return journey through unspoilt jungle to the 500-year-old ruins is nirvana. For those who don't like mud and mosquitoes, it's hell.
The terraced ruins of the Lost City are being touted as an alternative to Peru's overrun Inca Trail. While admittedly not as spectacular as Machu Picchu, what is remarkable about the Lost City is how unspoilt it is. Our group of seven were the only people there.
There are a number of reasons for its seclusion. The first is it is only accessible by foot through inhospitable terrain. The second is that the paramilitary activity that dominated the area years ago prevented the ruins from being developed and exploited.
A quieter reason is the farms near the ruins grow coca, the plant refined into cocaine. Colombia is responsible for about 80 per cent of the world's trade in cocaine and the illegal drug has played a massive role in the devastating internal conflict that has crippled the country for years.
Surprisingly, although we had signed up to see the ruins, the simple encounters with locals along the way turned out to be the highlight of the trek.
On our first night, we shared a meal with three generations of our guide's family at their farmhouse. The next night we camped with the military. On our ascent to the ruins, we passed through the villages of Kogi Indians, who have lived in the area for countless generations.
While just kilometres apart, each group has led a completely different existence, showing us there is no one way of life in this country.
Heading south, the city of Medellin is a convenient halfway point between the Caribbean Coast and the capital, Bogota.
Once the centre of Colombia's drug trade, Medellin was considered the most dangerous city in the world, though it has been reinvented as a sophisticated cultural centre. Large sculptures by renowned artist Fernando Botero are scattered throughout the city, which is festooned with flowers in summer, and it is the perfect base for exploring the colonial towns nearby.
But its dark past still lingers. Much to the chagrin of tourist officials, one of the most popular tours revolves around Pablo Escobar, one of the world's most notorious drug kings.
His shrine-like grave is strewn with flowers (ironically, he began his career stealing tombstones), while tours also visit the crumbling ruins of his custom-built luxury prison, La Catedral, and the abandoned house where he was shot after a 499-day manhunt.
Perhaps Escobar would have benefited from a visit to Miguel Caballero, a Bogota-based tailor who specialises in bulletproof clothing. His inclusion in the Lonely Planet guide has given him cult status among the travel set. Rumours abound that US President Barack Obama wears his collection, while legend has it he shoots his employees and there's ample proof on video website YouTube that he'll shoot international journalists on request. However, he does not shoot tourists for fun, despite guidebook-toting backpackers dropping past his small shop every few hours to ask.
The heart of Bogota is La Candelaria, the 470-year-old historic quarter, where narrow cobbled streets give way to a collection of century-old churches and the magnificent Plaza de Bolivar.
Although a number of excellent museums surround the old quarter, Bogota is hard to warm to. Even the statues of saints perched on top of the mountain ranges that rim the city designed to offer hope to the slums appear like an army of cranky archangels ready to swoop down on the anarchy below.
Salvation is on hand just an hour away at Zipaquira, a small mountainside town surrounded by dairy farms, where you can acquaint yourself with Colombia's other white powder: salt.
Here, an old refuge in a salt mine has been transformed by more than 100 sculptors into a stunning underground cathedral. The descent is haunting, with illuminated carvings representing the Stations of the Cross lighting the way. Gothic angels sculpted from pillars of salt line the walls while eerie optical illusions have been created with careful lighting throughout the caverns.
Sitting in this cathedral 100 metres below the surface, I'm able to see another dimension to Colombia, one strongly influenced by hope. Perhaps it is the country's unwavering sense of faith that has unified the population and helped them to survive such brutal times.
Colombia is a beautiful country with broad appeal but its colourful past will form an integral part of its tourism industry in the near future.
For travellers, Colombia's call is irresistible, a place with so much terror and so much beauty, a thin veneer of improved safety and a healthy dose of the unknown. And for me, the risk isn't wanting to stay. The temptation lies in wanting to go back for more.
Touring there Dragoman runs a 12-day "Salsa and the Spanish Main" trip from Cartagena to Bogota, including internal flights and accommodation, for about NZ$1900 with a kitty fee of US$340 (NZ$575). See dragoman.com. Kumuka runs a 10-day "Pirates, Dolphins and Mud Volcanoes" trip aimed at families. See kumuka.com.au. Treks to the Lost City leave every second day and can be arranged through Sierra tours. Prices start at $US265. Email email@example.com.
Blacksheepmedellin.com offers a comprehensive list of activities and destinations for independent travellers, as well as advice on safety issues.