Here's what I like
First I like Elemental: fallen something, like fallen enchantress, it uses what you already established and can build on it
Elemental: Fallen (whatever)
ex. Elemental: Fallen empires; Elemental: Fallen heros; Elemental: Fallen warriors; Elemental: Fallen age; Elemental Fallen mages; etc
Next I just like elemental and a second name; elemental might be damaged right now, but I think a sequel if its good, wouldn't just undo the damage done by Elemental: War of Magic, it could result in good publicity and press
Elemental: (whatever)
ex. Elemental: Age of wrath; Elemental: Time of sorrow; Elemental: Master of the shards; Elemental: Rise of kingdoms; Elemental: Reborn
Next I like Master(s) of Elemental, it keeps the name and also harkens back to MoM
Masters of Elemental: (whatever)
ex. Masters of Elemental: The shard war; Master of Elemental: Age of Heroes
Next I like something new, a complete rebrand. However, to complete the rebrand you should use hexes. Then even with the exact same style of game play and artwork anyone; you could say it is a different game because "It's obviously a different kind of game. It's hex based and Elemental was a tile (or square) based game"
Something New: Total Rebrand
ex. The Fallen Age: War of Mages; Fallen Empires vs. Kingdoms reborn; Fantasy Civ; Legendary Civilizations; Fantasy Realms; Fantasy Empires; Frogboy presents: A Derek Paxton design: The Fantasy Kingdoms: Hex based fantasy 4x: With heroes AND armies; or finally A very dangerous make believe world of magic, swords, strategy and heroes
That's my take on it.