Fah!  Fun by any other name is still fun.  Besides, I don't see anything odd about it anyhow.  + I'll wait to judge the names relevance once I learn something of the games lore.

BTW: The name is Fallen Enchantress

It's Enchantress. And it worked for Ultima 2, so why wouldn't it be proper for Elemental?

This is such a silly topic... talk about being over-sensitive on a minute detail when it comes to marketing.

You know, Enchantress suggests there is some magic or things involved. We wouldn't want to imply that the game will be "magically" better than EWOM, would we? Also, we should probably avoid any reference to magic altogether, so as not to upset the fundamental religious consumer base. Furthermore, I've been thinking about the name Stardock... to me, it's important to cater to all players, so to avoid any risk of alienating people that believe there are no stars, that they are ancestors in heaven, the company should probably rename.

Edit: So maybe some internet troll will find it ironic. Who gives a shit? Flamers gonna flame.

I shouldn't be doing this kind of stuff but I couldn't resist:

Name is fine.

Eh, this game is for people who are familiar with fantasy to have heard the term "Fallen" in reference to dark and evil to get it.

Ok, I have another minor issue. Even if one is familar with this use of the word 'fallen' from general fantasy, if you don't know this particular story, you wouldn't guess that it is not necessarly the enchantress that has fallen, but her background is among a fallen race of men. The name implies that she was once good and pure, but then changed and now she is thus 'fallen'. Really though, someone else did the falling, she's just staying down... The enchantress never actually 'fell'.

Ok, new name. 'Enchantress of the Fallen'. 

Elemental*: Dark Oracle**

* minorly related to the Elements as it really refers to the name of the World.

** Dark because she is "evil" (at least by Kingdom propaganda) and Oracle because she is one and seems to make her more unique than Enchantress, Magician, Weaver, Spirit Bender, That Who Talks With The Kami, Veil Piercer, SQL,...

fallen angel? to me, the fallen part wasn't really ambiguous (I never imagined an enchantress stumbling about and falling down a flight of stairs) . I like the title, but admit that if I'd never had heard of ewom and FE and saw this in the shelfs, I'd probably overlook it. Stardocks 'demigod' on the other hand just caught my eye because of the title (and introduced me to stardock that way *g*). for books etc I also often browse through the titles until one springs out, only then I look closer, read the summary etc.

Anyway, I hope the title will attract newcomers as it certainly deserves.

Elemental: slightly depressed sorceress has misplaced her pills - if you find them please call 1-800-749-3153.

Elemental: The Boobs of the Enchantress

I'll let yourselves to imagine the proper cover for the box.

And the new gameplay elements (those also sell).

(seriously though, yeah, titles sell, covers sell, gameplay sells.... and yet they don't guarantee it)

Hm, I don´t really get why "Fallen Enchantress" should be a bad title?
I mean, honestly, how silly is it to assume, people would associate a person who has fallen to the ground?
Wouldn´t that rather be a "Clumsy Enchantress"?

Yeah, being critical is a good thing but there also is a being ubercritical.
If we assume that the targeted customerbase doesn´t get what "fallen" and what "enchantress" mean, we can assume that almost NO title would be "save" and unmisunderstandable.
Even more, the targeted customerbase seems to be a small fraction (EWOM-users and -interested) of a fraction (fantasy strategy/4X gamers) of a fraction (fantasy fans or computer gamers) of a fraction (computer owners) of the people who could possibily misunderstand the title; I honestly assume that an overwhelming majority of these customerbase will instantly get what "Fallen Enchantress" will mean.

Apart from that, from the point of "Does it catch my interest?", I can´t find anything wrong with the title either.
As was already said - it is short, it contains "fallen" as in "fallen angel" as in "battle between light versus darkness", as well as "Enchantress" as in "Magic is an element of the game."; plus, as a bonus, the association with seduction, e.g. sex.
All in all, primitive as one may find it, a pretty catchy title, if you asked me.

PS: There is no such thing as perfection when it comes to naming.
So many associations mingle here, that there will always be people who don´t like a name, title, designation.
I still remember the discussion that arose when DnD 3e was to be translated into other languages; especially the terms "sorcerer" and "wizard" were highly debated because there were no exact synonyms for these.
In the end one has to make a decision though. That doesn´t free you from the responsibility to look for the maximum in accordance, but it means that you´ll HAVE to stop looking for it at some point.