Yeah, the Veep doesn't get to vote. Not only that, but if there is a Senate vacancy, it still requires 51 Senators. 50-49 doesn't cut it. (The same's true in the House. It takes 26 States positively voting for someone, even if some States are tied or not voting.)
I always assumed that if the 2000 election was challenged and there was a party line vote, Gore would have gotten to cast the tie breaking vote for his running mate.
If there was a motion on whether to accept the votes cast by Florida's electors, then Gore could have broken a tie on that motion, since it would be an ordinary vote of the Senate, But in the contingent election of a Vice President, he would have had no role except to preside.