I'd say as likely as the Persians were. Persian religions and traditions are, after all, much older than Roman ones, and the Iranian elite was pretty thoroughly Islamised by the eighth century, after all. If Iranians can become Islamic and then "Iranise", for want of a better term, the Islamic faith, I think it's quite plausible for Romans to become Islamic and "Romanise" Islam. You can see this sort of Roman influence on the Ummayads, after all, prior to the Caliphate's centre of gravity moving decisively eastward with the conversion of the old Sasanian aristocracy.
Well the Romans Romanised Christianity pretty well, so presumeably Islam would adapt in the same way if adopted by the Romans. Islam has quite a lot of local traditions absorbed into it all over the world, to accomodate the beliefs of the people of the region. This in turn leads to bouts of puritanical attempts to distill it. There is little difference from Christianity this way.
Islamic Romans, you could be cheap and have an Islamic claimant to be the successor of the Roman Empire (so basically the Ottoman Empire

) so lets say that the Sultanate of Rum conquers what in the OTL the Ottomans did and presto!
That's too easy, so to make it harder, let's make the united empire Muslim: Constantine gets defeated or Julian survives and is suceeded by a pagan heir. That way you have a more tolerant and pluralistic society. The Roman Empire then survives the Germanic invasions (if you don't want to make it a Roman wank then lets say they still lose North Africa, Iberia and/or Gaul). I don't think this implausible considering how long the Roman Empire had already survived, but then you have to not butterfly away Mohammed, and so lets say Arabia, in its relative isolationism, is united under Mohammed. The Arabs then send ambassadors to the Roman Empire, wherever its capital might be by the 7th century, and try to pursuade the Roman emperor to convert. The pagan emperor would probably not convert, but he would probably be receptive to the idea of allowing Muslims to build mosques and preach.
If you throw in some political chaos, or the Arab conquest of the Sassanid Empire, then Islam will seem more appealing. Maybe Arabia becomes an ally of Rome, or maybe it goes to war with them. Rome wins (assumed for the sake of this scenario) and the Arabs come into the Empire, but either way Islam comes into the Empire. Islam would probably be popular among the Christian population, which is likely to be a large minority, and could spread quickly. If we then just let Islam follow the route Christianity did (and I'll use this as a conservative estimate, though Islam in history spread far faster), then within 300 year you have the first Islamic emperor, probably as Islamic as Constantine the Great was Christian (which is very debatable). The Caliph could be another title for the Roman emperor or maybe the Caliph becomes simply an Islamic pope. Or maybe the emperors would cause a schism and this divides Islam between a Roman caliph and an Arab/Persian caliph.
Anyway assuming the emperor becomes a Muslim, this should pave the way for a Muslim Roman Empire by 1000 AD.