Emirikol said:
Avoid the "elemental" theme. It's boring, overdone, and cliche.
A different direction (forget about elements) could involve dragons. There could be decadent cities of Mojh (from AE), draconian soldiers, half-dragons nobles, and dragons slumbering in caverns. The four lands (which by the way are all surrounded by mountains) could be some sort of "forbidden country". Loosely based off Melnibone whose glory lies in its past.
Now dragons would be the masters of magic, not mere monsters waiting on their treasure hoard. They will have an important role in the campaign. So far I envision this:
-- Instead of a normal pantheon of deities in this setting, thre are evil alien gods on one side, and the dragons on the other side (still alien but less dangerous). So, the dragons have networks of servants of all sorts acting on their behalf.
-- Dragons are really magical creatures, not just creatures with magical abilities. For example, when they sleep, this is not mere slumber. It's before all because dragons spend much of their time wandering the world in Astral form. Not only the prime material plane, but also outer planes, etc. As a consequence, dragons knows many things, many secrets.
-- Many of the things that people believe about dragons are superstitions and misconceptions. For example, dragons do not necessarily (and in fact rarely) crave for material treasure (unless it is magic items). They crave for magic. In fact, these huge beasts feed essentially on magical energies in the Astral plane. They don't need flesh. When an evil dragon devours a person, it's generally to scare people, not for food.