Basically, make Andalusia into a Christian kingdom stronger than the other kingdoms in Iberia, which actually claims the "Empire of all Spains" title, yet, has not actually united the peninsula.
I don't see how to make it work : a basic yet overwelming part of identity of an Arabo-Andalusian hegemonic power (emirate/caliphate/sultanate) was it had to be based on the fight and supremacy over Christians kingdoms and periphery. It could be mostly theoritical and limited to annual raids or to subservient treatment of inner Christians, but it was still there (and remained to be so until 1492, at a point where Nasrid Grenada was more a Arabo-Maghribian state than Arabo-Andalusian), and justified the overlordship of any dynasty (Umayyad, Alid, Almoravid, Almohad) over the quarelling taifas.
You'd need so much a complete upheaval for what matters not just Arabo-Andalusian political and cultural concepts, but Arabo-Islamic concepts that at best, a PoD in the formative years of Islam would be necessary.
Not that you couldn't have local conservion (or rather, dynastic reconversions) to Christianity, but that's essentially a muladi thing, such as with Ibn Hafsun in opposition with Umayyads (admittedlt, he's the most extreme exemple). The localized, and ethnicized feature of this Christianisation was percieved as existentially threatening by the lot of Arab or more arabized muladi elite : while we could see Christian taifa appearing with an early fall of Umayyads in the Xth, it would probably go down at middle term as either reconquered by whoever get the leadership in the region, or absorbated by a regional powers (probably Fatimid if Islamic).
But the whole of Andalusia? I really don't think it's doable.