I like that Imperial Reconquest idea. I would suggest perhaps splitting the first tier (Greece & Anatolia) into, say, Thrace, Thessalonika, Nikaea, and Trebizond into the earlier tier and the rest into a later tier - this would be for late starts where the Byzantine Empire has already lost massive territory - it wouldn't make sense for them to basically go jihad on Armenia when they barely control Thrace.
@cybr: Weren't the Persians pretty tolerant to different cultures? If I'm wrong though, I'll remove the modifier from the Iranian culture group.
I'll consider giving the Italians and Iberians a watered down (20% maybe) version.
I dunno if the Persians were tolerant per se, but I know they didn't like the Arabs. Although this might just be a modern thing (I thought it occurred historically too - but perhaps that was only for the first half a millennium after the Arab conquest). Overall though cultural differences weren't as significant to much of the Muslim world, so I guess you can keep it for now.
Otherwise I'm pumped for the new version!
Edit: Oh, also, I think diligent characters should be able to do the IMperial Reconquest CB, too.