Please not many cameos here. If you do have a cameo, make it subtle, like a puzzle from another game, where someone who played the game says "I've seen this before!", or that sort of thing.
Here's a few ideas:
Madraz: This is Madra, from long ago. In the meantime, Madra has become a great civilization thanks to the power of Alchemy, and the wise mayors who have used it well. They managed to buy some boats off of Lemuria before it was destroyed by the Betrayer (I'm making an attempt to collaborate with Role's storyline).
Osenia Settlement: This was once Alhafra, but its name was lost long ago, as a series of greedy and corrupt mayors led it to its downfall shortly after the release of Alchemy. The current mayor still lives there, and still refers to it as Alhafra, but he is almost the only one still there, and everyone else just calls it "Osenia Settlement" or "Osenia Ruins".
Tolbi: Tolbi hasn't changed much, they still have Colosso, and it still has the Tolbi Springs, but it now has the Eclipse Summon, and is the only place that it can be obtained since Lemuria's destruction.
Sea of Time Ruins: The ruins of Lemuria are largely flooded, and is inhabited by water creatures, and strange living bursts of elemental energy created by the Betrayer's assault. It is also home to many zombies and ghosts of the people who once lived there.
Sea of Time Settlement: Some from Lemuria managed to escape, and are living in another section of the Sea of Time. They have built platforms on top of the many Grind-able objects throughout the region, and live on those platforms.
It is a harsh life, as they barely scrape out a living among the lifeless Sea of Time, and a good earthquake would knock their platforms into the water and kill them.
Northern Ruins: Ruins of the town of Imil, which was destroyed by the Betrayer. Many ice monsters live here, and Ravagers have taken over the area. This has also become an archaeology camp, and a large number of archaeologists scrape out a living as they defend their camp against Ravager attacks.