This map was helpful:
I took the counties with at least 2 coal mines (and excluded Jefferson County, AL); the two-party-vote was 64/36 Romney.
I had no idea there were coal mines in Alabama up until I saw this.
Not too many, but that's where the southern end of Appalachia is.
The map doesn't really correspond perfectly with the Appalachians though. The spine of the mountain chain runs through north Georgia, the NC/TN border and SW Virginia, but there aren't any coal mines in those places. As far as I can tell, the areas with coal are found in a long vein running a bit west of the Appalachians. That area of Alabama is very hilly but not mountainous.
I think that geologically speaking, they should be considered as the southern foothills (or highlands) of the Appalachian mountains. They are after all considered linked to the mountain chain by geologists.
Yes, I can agree to that. There are many areas of Alabama that are quite mountainous, but that area west Birmingham isn't quite as rugged, it's more like foothills, as you said.
A map I just saw of the region classifies the coal mining region as being part of the Cumberland plateau, just west of the blue ridge province.