I just played the 2000 scenario as Al Gore. (No, this doesn't mean that I am hopping on the Gore 08' bandwagon). I've determined that just about anyone in Gore's situation could have won the 00' election. I did with no whining and Nader at 5% of the vote. In other words, no challenge at all.
Gore/Lieberman (me) - 51% - 384 EVs
Bush/Cheney - 41% - 154 EVs
Nader/LaDuke - 5%
Browne/Oliver - 1%
What scenario? Most scenarios (including the ones given in the original game) are heavily biased in favour of Democrats. I remember the Gore v Bush that used to exist was heavily biased in favour of Gore, for instance.