Mujahid's problem was that he was too late. By 1016, the Christian maritime republics were strong enough to oppose such operations. An earlier fragmentation of Andalusia might allow someone like Mujahid to appear earlier; alternately, a different Italian situation which strangles Pisa/Genoa in their cribs could do the trick.
The problem with entrusting this expedition to a stronger Andalusia is that it's simply not a high priority. Why would you pay attention to Sardinia when the Christian kingdoms are right there, on your border? In contrast, Mujahid's state (Denia-Mallorca) was a coastal-facing principality whose only infidel "neighbors" were over the sea. Of course, nothing stops the taifas from fighting each other instead of Christians, but Mujahid's invasion was also a matter of legitimacy: as a "saqaliba," a former slave of Christian/Slavic origins, it was critical that he legitimate himself as a ruler. He produced his own puppet Caliph and attacked Sardinia to demonstrate his commitment to jihad and to establish himself as an "emir by conquest" who had expanded the house of Islam. A strong Andalusian Caliphate doesn't need to "prove itself" in this way, and if it does gain a renewed taste for holy war Sardinia is hardly the most likely target.
As for the Muslims of Africa, they could potentially have managed it in the 9th century, when Sicily was being conquered IOTL. Perhaps if Sardinia, rather than Sicily, was the site of a Byzantine rebellion, Sardinia would have been conquered instead. Sardinia, however, has a long history of resistance in the interior - even the Romans had trouble with the Sardinian natives - and the Africans might have some difficulty fully pacifying and settling the island. Even if they manage it, it's very likely to fall back into Christian hands by the 11th-12th centuries unless Italian history is substantially changed.