It could be that they’re related to the Phoenicians. The purple dye that the Phoenicians used came from a type of mussel, so maybe they’re “Musselmen” which became Muslim.
Very interesting thought, which may explain how they ended up in Hispania. "Musselmen" implies that these people had been fishermen with some reputation and this obviously means that they had a lot of ships. Which means that they could easily sail from one part of Mediterranean to another. Probably, it is not unrealistic to assume that at some point (say, after resources of the mollusks in the Eastern Mediterranean had been depleted by the extensive exploitation) they had been united by a charismatic and capable leader and sailed all the way to Hispania in a search of the new "resources". It is also not unrealistic to assume that the locals were not excessively excited by the new arrivals. One thing led to another, the isolated brawls evolved in a major war with the "Musselmen" ending up as a ruling elite (as Bulgars in Bulgaria, Scandinavians in Rus, Seljuks in Anatolia, Franks in Gaul, etc. ).
Not sure what they had to do with the "Arabs" (who, IIRC, never made it out of Arabia) or any specific religion.