What a fascinating discussion. Just to throw in something purely speculative:

The countryside surrounding Birmingham, AL was not very impressive to me when I was there just recently -- mostly rolling hills. The mountains of WV make a very impressive locale for stories about backbreaking work, all steep slopes and small valleys. A couple of different versions I've heard call him an "East Virginian man" (Eastern West Virginia?) It seems possible to me that the WV locale would be more popular or more believable from a legendary point of view, and therefore better fodder for storytelling, regardless of his true origin.