Conversion to dynamic demographics would be the ideal fix.
But I do think a good, workable, and relatively easy to implement fix would be to change some region types on the existing maps, and edit their appearance, to create new cities/strongholds.
That's the kind of thing which wouldn't require the complexity of changing region connections or creating new regions from scratch, but which would make a major difference to game play.
