Gore is not a charismatic personality and campaigner like Clinton.
Gore is not considered by the south as someone who any longer represents their interests, therefore, he fails to win southern states, with the exception of his home state, Tennessee.
Graham fails to deliver Florida. It's close, but Bush wins the state.
Bush puts together a winning combination in a tight election.
Bush/Quayle 270
Gore/Graham 268
Perot/Stockdale 0
You are the Naso of historical elections. Gore happens to have still been a Senator from Tennessee. He was not an extremely charismatic Governor of Arkansas, but he'd definitely win, and by a decent margin.