Recently I have been reading about the late bronze age in the near east and I came across many references to cities like Cairo, Damascus, Baghdad (or at least the equivalent at the time). However, I remember a book by Richard Bulliet (if I remember correctly) in which he explains that Muslim entrants into the Levant and Mesopotamia settled into newly founded cities in order to escape the factionalism of existing politics and to distance themselves from non-Muslims who might chafe at them, and to have a more secure location.
So who is correct? Were Baghdad and Damascus founded by the Muslims or were they older?
They're both correct, the key distinction that you're running over is that little parenthetical "or at least the equivalent at the time."
So in Cairo for instance you can point to Babylon fortress as evidence for "first settlement in Cairo" being ancient. But at the time the Arab settlement of Fustat would have been a "new city." Today both have been completely surrounded by the modern city of "Cairo."
Generally speaking, however, the modus operandi of the conquering armies was to create new settlements just outside the major population centers. The most famous of these are probably Fustat (Cairo) and Kufa, which is about 10km outside of Najaf. Today it's usually a distinction without a difference as, at best, as in Cairo, the "new" Muslim city will just be a neighborhood of the larger metropolis.
The two noteworthy exceptions are Baghdad, which was founded long after the conquests as a city designed to be the capital of the empire, and Arab settlement of Khurasan, which is worthy of mention for the role Khurasan came to play in Islamic history. Basically huge numbers of Arabs settled there which, to give a massively shortened TL;DR may have triggered the Abbasid revolt and also played a large part in why that seemingly isolated region became a major center of art, culture, and the key to military success for centuries.