Obama 410-128
I think it's unlikely Bush Jr. would have been reelected with a pro-choicer as his VP, but following your scenario, Obama wins in a massive landslide because he could easily tie Giulani to Bush Jr.'s unpopulairty (and do an even better job on that than he did with McCain, as Giulain is Bush Jr.'s VP). Also, Giuliani's support of abortion would cause a lot of moral/Evangelical voters to stay home. Finally, Giualini's corruption allegations and lack of charisma will also hurt him.
Giuliani solidly loses the Dakotas with John Thune on the ticket? Thune doesn't even have a willing opponent in his Senate race this year.
Oh sorry, that was a mistake. I meant to have both Dakotas vote for Obama in the 40s. There, I fixed it.
How does the Republican ticket lose them at all with someone as popular there as John Thune on it?
Obama lost both Dakotas by high single digits. Due to Giuliani's support of abortion, many Evangelicals/pro-lifers would either stay home or vote third party (or vote for Obama, if they are liberal on economics). Thus, I could see the Dakotas flipping to Obama in a race against Giuliani. Not to mention taht McCain amanged to distance himself from Bush a little. As Bush's VP, Giuliani would have been unable to do that.
Even McCain got tied to Bush. Bush was so unpopular that if Rudy really was Bush's running mate in 2004 and the nominee in 2008, then I think just about anything is up for grabs for Obama. Texas could go his way and even most of the south. I don't know if Giuliani breaks 100.