The Romans definitely were Christian at the time of the conquest. Many Berbers were Christian as well. Catholic bishops continued to exist for several hundred years after the conquest and they even kept in contact with Rome through letters. Islamization wasnt instant.
I get all that but the timeframe that the Reconquista of North Africa would have to be after the Recoquista of Iberia was finished, and that would mean that any attack would have to be later the 1500's when I doubt there were many Christians at all.
However looking at the original post it seems to be talking about an internal Reconqusta, not one from Spain which is what I was talking about, so my bad.
For an internal one, the focus would have to be on the Berbers, which is quite possible since as you said there were a lot of Christian Berbers. The year it happened would play a major part, obviously the closer to the conquest it was the easier the Renoquista would be.
There are several things that would have to happened to make this possible. One is no Donatism heresy. It was huge in North Africa and splintered the Christian community and made Byzantine and Rome more hostile to them. I wouldn't be surprised if there was some writing saying the conquest was Gods punishment for North Africa. If the Berbers were more integrated into Orthodoxy, then the church would have been able to stay together, discounting the idea of a Byzantine attempted reconquest being more successful with greater support of natives.
If there was a stronger centralized and Orthodox Church, it is much easier for there to be monastical orders set up (Donatism beliefs seemed to be against them) A stronger Monastical order would allow a stronger church and a definite rallying point for the people, taking pride in there own people, bringing up there own saints etc.. This would be especially important when the Umayyad Dynasty started there oppression.
IOTL the Berbers fell under Khawarij banner, which treated people equal and was a good fit with the more nomadic and more egalitarian Berbers. However, if there was an area of support for local monasteries and monks, I would guess the people would fall under that banner, the banner of the local figures that had been around and important parts of the community for hundreds of years. And even if the revolts failed, rebels would definitely be around in the interior for years to come and keep an resistance up.
IOTL, Islam just chipped away at Christianity until it was too weak to resist, the fact they were tolerant for the most part helped them immensely. However if the Berbers had a stronger base, they would be much stronger and could possibly resist when a Almohad type forced conversion came along.