If I get this right the OP is : What if a early fitna lead to a Fatimid invasion, if Abd al-Rahman failed to unify the peninsula?
That's actually technically doable, and historically some of the rebels,
ibn Hafsun in particular, acknowledged fatimid overlordship.
Still, there's several points that would represent an issue :
-
Fatimids were Chiits. Religious identity was in middle ages the main identity factor, and islamic or ismalised population isn't going to be that much enthusiast about it. Ibn Hafsun "forgot" to tell his followers about that, for instance.
-
Maghrib : the whole region served as a shield between Ifriqiya (whatever fatimid, aghlabid, or else) and Al-Andalus. By the IX century, it wasn't yet controlled/clientelised by Cordoba but the mosaic of berber states and tribes is going to represent an huge obstacle.
OTL, it was done by the fourth fatimid caliph, and it was no little feat.
-
Emiral power : at the end of IX and beggining of X, the population grew really tired of the wars and wanted some maintened peace. Contrary to OTL Fitna era, where the caliphal authority was gone, due to no caliph, the young Abd al Rahman still had some ressources.
A bigger territory than the caliphes wannabes in the XI, tributes from autonomous and independent governors, and a still rather intact institutional authority (if challenged).
-
Arabo-andalusian rebels (please make the distinction there between Arabs, Arabized, Berbers and Christians : the andalusian society was really divided along these lines) are more likely to follow Cordoba's against a threatening berber dynasty.
It could even be one of the reasons why Abd al Rahman III did managed to retake control of the peninsula historically. While taifas eventually called for help berbers and relativly not fought them after, fatimids would be probably more fought against.
-
Egypt a no-go : Egypt was wealthier, more vulnerable. You'll need to change it so that it looks less tempting as a prey than Spain.
Assuming fatimids manage to bypass all of that, I suppose that they could conquer a good part of Al-Andalus by the end of X century.
It would be quite changed than OTL : a failing caliphal authority would probably mean a more successful Asturias/Leon. Both by conquest, and by influence (forcing tributes on neighbouring Muslim governors).
Of course sucession crisis would probably still happen somehow, but Leon would have a better chance overall even if fatimids could pull and almoravid on them.
If Banu Qasi (depending on the PoD) manage to keep an hold on upper and/or lower Ebre valley, you could have a relativly important Muladi state in N-E Al-Andalus (
if it helps, a map) that could, if fatimids try to do it smoothly, serve as a buffer region between Franks, Leonese and Fatimids in the region.
Finally, as Fatimid conquest would depend eventually on allies they could have on the peninsula, I suspect that Ibn Hafsun-like rebellions would be awarded with lands, autonomy if not independence de facto.
Eventually, a fatimid victory could have meant a muladi political victory as well.
Would fatimids have been able to make a lasting conquest? I don't think so.
The issue with Ancient North African empires is their tendency to split up really quickly : OTL fatimids have just conquered Egypt when Maghrib and Ifriqyia get off the radar, Almoravids and Almohads had to pratically use Al-Andalus as an autonomous viceroyalty in order to keep it.
They key is the control of Maghrib : once lost, keeping control of Al-Andalus and North Africa in the same time is more than tricky, and fatimids wouldn't have power bases enough in Spain to afford loosing North Africa too soon.
Finally, the structural instability of medieval islamic states isn't going to help at all.
In the meanwhile, they could introduce shia introduction : historically, some tried to go it smoothly (as mentioned, introducing shia prayers without telling people it was shia prayers) but at the end it would have been pretty obvious.
I suppose a indigenous shia elite could appear, but definitely not Arab : probably Muladi or Berber.
I know the Ismaili faith of the Fatimids will make paving their way in Sunni Spain a bit rocky, but I think that's part of the fun.