You'd need to turn McCain against Bush pretty fiercely. I'm not exactly sure what could have made him turn towards a Bush backer this year besides party loyalty; the 2000 campaign against him was pretty low and it's hard to imagine something much nastier.
Maybe the reaction would have been different? The stress of the attacks cause Cindy McCain to relapse in her drug addiction, and she dies of an overdose shortly after the general election. McCain blames Bush for his wife's death, and leaves the GOP when the new session of Congress is formed in January 2001. As an independent, he caucuses with teh Democrats, giving them 51 seats and is named the chairman of the Senate Foreign Relations committee, where he regularly spars with the administration.
The Democrats gain seats ITTL in 2002, and thus no longer need McCain for a majority, leading them to move leftwards and McCain stops caucusing with them and instead is a true independent in 2003 and 2004. He runs for the Presidency in 2004, and Lieberman, soundly defeated in the Democratic primary by a more anti-War candidate than Kerry (Dean? Or Kerry himself with a different strategy) joins the ticket that sumnmer.