Louis XXIV
Le Roi Soleil
Dido has more historical sources than just the Aeneid. Going by additional sources, it is entirely possible given the time period that she was the first ruler of Carthage, albeit probably embellished in certain respects.
There's no Carthaginian stories, though, and I'm pretty sure they do have a documented foundation story. Are there any non-Roman sources? Greeks were enemies too, but that's at least a start.