Actually, Andalusia is Arabic in origin; it was dubbed "al-Andalus" ("country of the Vandals" - the post-Roman invaders) by the Moors who came in the 7th century. In the 11th century, when the Christians took the area back over, they retained the "Andalus" part and Latinized the original meaning to Andalusia.
Anneza's statement about Roman territorial naming customs sounds right in many circumstances, but they called the area Baetica (land of the Baeti?).
Sometimes the good ol' 30-volume Brittanica just beats the pants off the Internet, don'cha think?