Yes, if you look at Dave's data on the state, many traditionally Republican counties voted for Easley against Ballantine in '04. Something about the man was able to charm them, so maybe that would work in other red states. Mike Easley would be a great candidate because you're right. We (democrats) need a moderate Southerner with some liberal credentials and loads of charisma. I believe Easley fits the bill, but I don't know if he has any desire to run.
If nothing else he could be a good VP choice. Maybe a Warner/Easley ticket would work; two moderate Southerners from adjoining states worked for us in 1992.
I would think that a Warner/Easley ticket would win Virginia (except against Allen) and would have a pretty good chance in North Carolina. Tennessee, Arkansas, West Virginia and Louisiana would also be very competitive.