There are five distinct Clinton-but-not-Obama states that Bill Clinton won twice and Barack Obama got clobbered in -- twice: Arkansas, Kentucky, Louisiana, Tennessee, and West Virginia. Also of interest will be Georgia and Missouri.
state Kerry loss '04 Obama loss '08
AR 54-44 59-39
KY 59-40 57-41
LA 57-42 59-40
TN 57-43 57-42
WV 56-43 56-43
GA 58-41 52-47
MO 53-46 49-49
If you can see a pattern -- tell me what it is. I'd like to know.
2000 would be needed to see a pattern, IMO. Those are traditionally Democrat-friendly states, some of which still prefer Democrats locally and/or for the Senate, but they're simply not going to vote for a liberal from Massachusetts (and also a lousy candidate) or a Black liberal from Illinois.
state Gore loss Kerry loss Obama loss
'00 '04 '08
AR 51-46 54-44 59-39
KY 57-41 59-40 57-41
LA 53-45 57-42 59-40
TN 51-48 57-43 57-42
WV 52-46 56-43 56-43
GA 55-43 58-41 52-47
MO 50-47 53-46 49-49
Bill Clinton won every one of these states (but Georgia only once); neither Kerry nor Obama ever did (although Obama came close to winning Missouri in 2008)
Despite winning by landslide margins in the Far West and Northeastern Quadrant of the US, Barack Obama lost the Louisiana-West Virginia arc almost as badly as Walter Mondale did in 1984. That could reflect a 'poor match for political culture' more than anything else. Kerry was a horrible match for those states, too.
Georgia and Missouri may now be more similar to each other politically than any two other states even if their histories are very different. (Greater KC +St L within Missouri = Greater ATL within otherwise arch-conservative states?) I can hardly predict how they go in 2016, except that they probably go together.
Now let's look at two states that Bill Clinton never won -- VA and NC:
state Gore loss Kerry loss Obama WIN
'00 '04 '08
VA 52-44 54-45 53-46
NC 56-43 56-43 50-49
The (white) swing vote between 1996 and 2000 in the South can vote for a Southern Democrat attuned to and connected to Southern political culture, but not for a d@mnyankee Northerner. Gore may have been from Tennessee, but he forgot his Southern political roots. Barack Obama ended up with the non-swing Democratic vote in the Mountain and Deep South (unions and blacks). Gore and Kerry still did well enough in the Northeast, Midwest, and Far West to come close (Florida would have won the election for either) but did badly elsewhere.
Northern Democrats readily vote for a Southern moderate against a right-wing Republican.
Virginia isn't really Southern anymore. Since 1948 it had voted for only one Democratic nominee for President before Barack Obama (LBJ in his 60-40 blowout). 2008 may have seemed a fluke with Virginia, but 2012 showed otherwise. The state is becoming almost Northern in its demographics. Early polls show Hillary Clinton with unambiguous leads in Virginia and North Carolina.