The ideal time for this would be before the rise of the Fatimids which put a lot of strength into the area as the base of support for the new Caliph, but also before the rise of Abd Ar Rahmann III who fixed the mess that was al-Andalus, constantly beset by Muwalladun and Berber revolts, as well as the rise of Ibn Hafsun.
Ibn Hafsun converted to Christianity after all and still held onto a big base of support. Perhaps the Berbers of the Maghreb could unite with him and join his rebellion? The Abbasid Caliphate had little to no authority in the region anyways. It wouldn't be crazy that a Berber Revolt could have a syncretic Christian character that over time could develop into being more Catholic.
He is an interesting figure but his conversion to Christianity seems to have simply been a pragmatic decision. If he worked with the Berbers, he would have likely reverted to Islam.
647:
Flavius Gregorius loses at Sufetula, but isn't killed and retreats with his ungodly large Berber horde (c. 150,000) to the Tell Atlases.
648:
Uqba ibn Nafi returns the next year and invades Byzacena, occupying all of the province except for Karthago, but is unable to push into the Tell Atlases
657:
Flavius Gregorius dies of a stroke, and the Arabs push them south into the Inter-Atlas Highlands.
700-800:
The Arabs conquer Hispania, but most aristocrats move there instead of the Maghreb. In 750, as the Abbasids overthrow the Umayyads, the Christian Arab reconquer Mauretania.
An Islamic Hispania is only possible if the Arabs had conquered the Maghreb and if they still did, that make make the survival of a Christian Maghreb harder.