Some very interesting ideas, and an excellent debate so far...
Personally, I think if Constantinople falls to the Muslims we have a total deal-breaker there: the entire Mediterranean zone will be hard-pressed to stay out of their hands. Europe north and west of the Alps staying Christian? Maybe...
If the Caliphate had taken Constantinople, I agree that the capital would have been transferred there. Although it's in a cooler, more temperate zone, far away from the arid lands familiar to Arabs, the glory of taking over the capital of the Rum - the greatest city in the world - would mean the political and military elite would move there pronto, and the consequences of that act would play out gradually thereafter.
What happens next depends a good deal on what happens in the Syrian/Mesopotamian heartlands of the Caliphate. How far east do the victorious armies go? What sort of theology of Islam emerges? Who controls political power, and what is its basis?
I think Anatolia and the Balkans would quickly see the attractions of Islam. Sure, the underlying populace will (as in Syria, Palestine and Egypt) remain Christian for centuries - but men of ambition will quickly want to be a part of this New Order, and economic players in the cities will soon be wanting to be rid of the poll-tax on their 'protected' status, so the very best of Armenians, Thracians and Greco-Romans will soon be converting to the New Faith.
If nothing else, large numbers will be powerfully persuaded by the speed and decisiveness of the conquests: God is angry; Christians have sinned and fallen away from true Faith; it was wrong to believe in the divinity of Jesus; Muhammad is the Seal of the Prophets etc - and the fall of Jerusalem and Constantinople would be the proof. From this sort of teleological thinking a powerful impetus is likely to emerge from within this all-conquering Islam: New Rome is down, now to take out the Old Rome and complete Allah's victory. That's why I think a Battle Royal will rage over Italy. The Caliphate's ideological directors will become consumed with capturing Rome - possibly (probably even) to the exclusion of properly thinking about the proper organisation, administration and (crucially) the coalition-building needed in the Eastern provinces.
I predict that the rough Arabs will soon be left behind by the new ex-Roman, Muslim, elite, who will advocate more elaborate, bureaucractic, government and vast, lavishly decorated mosques (probably
with figural images) - unlike what happened in our timeline (relatively 'egalitarian' and Arab government - until the Abbasids emerged - and austere imagery in mosques).
I think the Romans would influence Islam to absorb more Aristotelian, philosophic and rational elements - encouraging a more 'Western' mode of interpreting Sharia, Hadith and other sources of the Law. The influence of secular Roman Law will also be enormous. It would encourage Islam to develop a distinction between the secular and the divine very early on.
Meanwhile, it would be inevitable that a Husayn ibn Ali-type figure would emerge: advocating that religious-political authority should descend through the bloodline of the Prophet instead of residing with the generals and the collectivity of the "scholar-imams" (the Romans would also influence this institution, and I agree a 'priesthood' is likely to be the template adopted - and the tribal, egalitarian, Arab model overriden). It would then be logical for the Eastern Caliphate to secede under its charismatic, tribal, blood-line supporting figure. There would be a powerful pressure for the Old World of West v East, Rome v Persia to be reborn in a new guise.
What would happen to Christianity in this scenario would be very interesting. I can see the Church reorganising in Italy if the Byzantines fall. But if Italy falls too, there will be a huge crisis of confidence. Rival Churches or Patriarchates may emerge north of the Alps, in Frankia or Spain (until that falls) but the prestige of Islam would be almost unstoppable. I quite like the idea of Britain becoming the bastion of surviving Christianity, personally, with a Pope of Canterbury etc-

- but this could only happen if Frankia, Germania and the rest of the north stay Christian - and come to view Britain as their 'Holy Isle' (not a warring, barbarous, mess as in OTL 7th century). And this 'rump Christian' area would come under severe pressure to convert in the centuries which follow.
I think it follows that peoples like the Bulgars, Avars and Khazars would convert to Islam if Constantinople is the centre of the Caliphate (so there goes Eastern Europe and the Slavic realm), although, if Eastern Islam splits off from Western Islam, the area north and west of the Black and Caspian Seas could become an ideological fault-line between the two strains of Islam.
Anyway, this has turned into a much lengthier piece than I anticipated!
Look forward to watching the discussion unfold further...