Perhaps because the AI in Civ only needs to worry about building its towns and normal troops, while Elemental's AI needs to worry about keeping its Sovereign alive, recruiting heroes, equipping heroes/sovereign, leveling heroes/sovereign, fighting monsters, doing quests, clearing goodie huts..
Civ AI needs to worry about tech, diplomacy, religion, culture expansion taking out resources, strategic resources, goody huts (yes, they have them too), quests (there are some in Civ IV although I'm not sure the ai can get them).
The real difference is that EWOM has tactical battles, and that's something immensely complex which Civ IV didn't have.
As for Brad's track record, Galciv (and Galciv2) definitely had great ai, but these games were even simpler than Civ. For instance, you need zero map analysis in space, and so there are basically no chokepoints. Now in Elemental or Civ, you have impassable mountains, and thus mountain passes to handle for instance. So even with his track record, there are many tactical difficulties in EWOM that he hasn't coped with in Galciv. I'm still confident he can provide a good ai in the long run.