You only have to go back to 2000 to find the regions voting roughly the exact same way (still GOP), with the Republican trend in eastern Tennessee beginning in 2004 with favorite son Al Gore off the ticket (Edwards' impact in North Carolina seems negligible looking at the results). Another thing to bear in mind is that the Obama campaign devoted considerable resources to North Carolina, and this includes even areas of the state they are not going to win, just to make the statewide total all the more likely to go their way.
I do see the same counties voting like this in '00 and '04 so I guess this is just one of the oddities in election politics.