How did the fall of the Western Roman Empire affect the spread of Islam?

So, let's set the stage first for the conditions that existed around the Mediterranean in the mid 7th century, when the Arabs began their rapid expansion.

In Iberia, the Visigothic Kingdom ruled over a relatively ethnically diverse group of people, but the Visigoths themselves were a very small proportion of the population, certainly under 5%, and formed basically a tight ruling class.

In Gaul, the Frankish Kingdom was roughly established over the territory we now recognize as France, however, it was still a relatively undeveloped territory. By this time, it is still likely that much of the burgeoning bureacracy of the Kingdom was still carried out by the Romanized inhabitants of the former province, while the kingdom itself remained relatively decentralized due to the German practice of dividing up lands between sons. In theory this was meant that the Kingdom itself was not divided, but merely administration of territory was. In practice, you can see how it might give rise to infighting (one of the reasons for the decline of the Merovingians).

In Italy, the Lombards ruled most of the peninsula, with a power base in the North (modern Lombardy). Within the peninsula, concentrated on the boot and in Sicily, Byzantine control remained nominally, although it was a house of cards waiting to fall. The South of Italy was a completely despoiled place compared to what it had been like prior to the Gothic Wars, and could offer little to help the Eastern Empire.

In the Balkans, the Avars and then the Bulgars pushed past meager Byzantine garrisons from the North and ran amock, basically destroying Byzantine control here for generations.

In North Africa, a relatively independent Exarchate of Africa existed, but most of its troops had been robbed early in the 7th century by the future Emperor Heraclius's invasion from there. The same Emperor who led Byzantine forces against the Persians and early Arab onslaught.

Finally we have Asia Minor, the Levant, Egypt, Mesopotamia, and Persia proper. These areas had all been devastated by the last great war between the Persians and Byzantines. and though the first three were retaken by Heraclius, that war had devastated both polities.

So, how does the fall of the West enter into this? Well, I'd say in two main ways. Most of the areas conquered by the Arabs initially were ones that were seriously compromised by that last Persian war. Egypt, the Levant, and then Persia; all were in serious trouble before this happened. North Africa fell quickly after, largely thanks to the already tenuous Roman control over the territory.

And here's the rub. If the Empire had been united and strong as it had been in the time of Diocletian or Constantine, the Persian invasion never happens most likely. Or at least, it wouldn't have been nearly as devastating as it was. The hallmark of the successful wars against Persia in earlier Roman history was the concentration of manpower against the threat. In this case, the Roman Army also would have been much more able to deflect the blow of the invading Arab tribes. The type of governance in the Post-Roman world in the west also is to blame here. Both in North Africa and Iberia, the territory was ruled over by non-ethnic elites, and when those elites were replaced there wasn't much there to prevent the Arabs from taking over and replacing them. All it took was one major battle for most of the Visigothic power in Iberia to be wiped out for example. Because the local populations often had little to no integration into the ruling structure in these territories, cutting off the head meant the entire control over the territory was extinguished. One could argue that the Frankish appropriation of local elites into their ruling strata contributed greatly to the success that Kingdom had in comparison to the Visigoths. Indeed, coming back to North Africa; when it was conquered by the Romans again in the 6th century, the destruction of the ruling Vandal elite (who also had not effectively integrated locals into their ruling structure) meant that the campaign was over relatively quick. Surprisingly quick actually, to the Romans.

Compare that to the Arabs. It was in fact Berbers and at least partly Berber elites from North Africa who made up the bulk of the invading armies against the Visigoths. The ability of the Arabs to quickly and effectively integrate the conquered peoples into their growing empire was one of the hallmarks of their spread actually.