For those headed to Cartagena in the future, a few places to try:
Enoteca - Italian, in El Centro
San Pedro Claver Restaurant in San Pedro Claver Square (it's a yellow building, you can dine in or outdoors)
La Tinaja- AWESOME Colombian food. Near El Centro. Dine outdoor under gazebos.
Cafe del Santisimo - El Centro
Glutton's recs are good. I would only add that there are a few old restaurants in la Cuidad Vieja with menus painted up on the walls. Selected dishes can be quite good, inexpensive. I also went to the beach when the fish catch came in, got some fish, and was allowed to cook it in the hotel.