I agree that Arcana Evolved is a good fit.
The following changes would have to be made:
-insert some sort of priest dynamic, probably a feat tree based off of the basic priest feat and only open to certain spell casting classes in certain regions
-various profession based feats such Merchant Rogue, Barber, and the Arabian Bard. You might even set that up as fairly comprehensive and make people take at least one at character creation.
-you would have to insert a charisma based genie summoning class.
-develop horse and camel totem warrior groups for the desert riders.
-you might think about some sort of alternate dynamic for warmains since they are going to be somewhat crippled without the ability wear heavy armor.
A lot of this stuff has actually been developed by fans of AE.