I completely agree that trying to market FE as something completely new and different would be a horrible idea. Frankly, it would be a total lie and would only likely only frustrate and annoy gamers and reviewers.
This is still a fantasy, TBS, 4X. Same world. Same characters. Same lore. Same basic mechanics (shards, channelers, etc.). Many of the same art assets as well. If someone picks up a screenshot of both games, they will easily see the similarities.
I have little doubt that FE will be a much better game than WoM ever was, and I have little doubt that it has tons of new characters, art assets, etc. However, this is not a 100% new game. It started life as an expansion and grew from there. It really is a reboot by most definitions, and there is nothing wrong with that.
Be up front about it. You guys earned a ton of good will by taking responsibility for the failure of WoM, and then being very open about FE. You can continue to earn good will by being honest, and may even get more credit if the game is really good, since it will stand in such stark contrast to WoM. That doesn't mean that you focus more on the failures of WoM than the hopeful success of FE. It just means to acknowledge the first while highlighting the second.
I say just call it Elemental: Fallen Enchantress. Don't try to call it Elemental 2 or anything. Call it a new game in the Elemental world, but don't shy from the connection to WoM. Executive summary / preview blurb wise, go with something like, "We acknowledged the failings of WoM, brought on some of the best talent in the industry, and reinvented the game from the ground up to create an amazing, modern fantasy 4X TBS game."