Every time I've encountered a reference to the origin of the name Andalusia, it has been stated that it is derived from the Arabic Al-Andalus and means Land of the Vandals. The Vandals, as we remember, were a Germanic tribe who, besides "vandalizing" Rome, worked their way into the south of what was left of Roman Spain and set up shop. Then, in the mid-400s AD, they crossed the Straits of Gibralter into North Africa, to annoy and then crush the remnants of the Romans there. They evidently all crossed, and left Spain open for the Visigoths, who replaced them as overlords of Spain.
But it turns out that here are several expanations of the origin of the name Andalusia. I'm reading a book, God's Crucible: Islam and the Making of Europe, 570-1215 by David Levering Lewis. Lewis tells us that Andalusia is a corruption of a Gothic phrase, landa-hlauts or "land lots", referring to the various landholdings of the Visigoth nobility.
I decided to check this out on Wikipedia, and there found also reference to Al-Andalus being proposed to mean Atlantis, and thus having nothing to do with the Vandals. Also, it turns out that there are several places in Spain that predate the Arab-Moorish invasions named either Andaluz, or having Anda or Luz as part of their names. And considering that the Arab-Moorish invasion of Spain occurred centuries after the Vandals had packed up and left, and been replaced by the Visigoths in what is now Andalusia, why would the Arabs have called the region Al-Andalus and not Al-Visigothia?
Wikipedia makes it clear that there is now no definitive consensus on the original source of the word Andalusia. Interesting. Right up there with speculations on the origin of the word "flamenco".
Carlos