Spanish native here. Andalusian accent never was known by being difficult to understand. Have other associations, but never that it's difficult to understand.
West Andalusia, maybe; but the Eastern accents plus Murcia are hard-drunken Irish mode for Spanish.
Some Andalusian accents can be really thick, but so can be the accents from other regions. It also depends where from Spain you are from: I am from Extremadura and usually don't have any trouble understanding even the strongest Andalusian accent, but some of my Basque and Catalonian colleagues find it really difficult, but the opposite is also true.