2004
To Bush--Alabama
To Kerry--Vermont
Gore actually broke 40% in Alabama, and won a few counties in the northwestern part of the state which Kerry and Obama both lost. Presumably these areas had a pattern of whites voting Democratic which has since reversed like many other areas of the South.
These counties were Colbert, Lawrence, and Jackson (the final one being in the northeastern part of the state rather than the northwest). I found Jackson the most interesting, largely because the swing from 2000 to 2008 is rather incredible.
2000:
Gore - 50.63%
Bush - 47.33%
2004:
Bush - 56.76% [this being the first time since 1972 that the GOP carried the county]
Kerry - 42.49%
2008:
McCain - 67.47%
Obama - 30.54%
The county is 92% white and much of it is located in the Appalachian mountains. According to Wikipedia, the county has a Dixiecrat tradition and its local government has no elected Republicans.
In 2004, Bush won the other two Gore counties by 10+ margins. In 2008, McCain won them by 20+.
It's pretty clear that the folks in these counties didn't like Obama's tax plan.