Cartagena de Indias is a terrific place. Sure, probably a bit dodgy if you’re walking alone at night on the wrong street… but still, it’s a terrific place. I’m no connoisseur, but I found the colonial architecture within the old city walls impressive. Especially the door knobs.
I was traveling with this French guy and we got into town a bit late, crashing at Hostal Marlin (dormitory costs something like 5 Euros per night) — no complaint whatsoever. The French went to sleep since he was tired, and I went for a stroll towards the city center. There wasn’t much going on, apart from this guy out of nowhere who started walking along, asking me all sorts of questions. There was no clear danger, of course — but it was late. I did my best to chat up to some point, be polite and later sending him his way by offering a couple of cigs.
Also, if you visit Cartagena do yourself a favor and — at the very least — try to find your way to one of the beaches such as Playa Blanca, alright? You can get there by bus plus taxi-bike or something, then sleep on the beach (in hammocks and stuff). Also, the last boat ride of the day back to town is something worth it (unless you get easily seasick, that is).