It's easy to forget now, but Bush was a really strong candidate in 2000; a year before the election, he had the
highest favorability ratings of any recent presidential nominee. Bush's "compassionate conservatism" and record in Texas were well-calibrated to make him appeal to both the right and the center, and even people who didn't like his policies generally saw him as a likable guy who was devoted to his family.
Meanwhile, Gore was a mediocre, charisma-challenged candidate (though I personally think he would have made a pretty good president) who distanced himself somewhat from Clinton despite Clinton's 60% approval ratings. And it seems pretty likely that a significant number of people who did approve of Clinton's overall job performance were also tired of the drama of the Clinton years and looking for a change.
