Condi is very tied to Bush, but, as a moderate, while she'd have trouble in a GOP primary, her social policy stances would allow her to run as a change agent, regardless of her foreign policy stances, and being African-American herself neutralizes Obama's massive advantage there, and assuming Obama doesn't pick Hillary or another woman as his running mate, she'd have an advantage with women too, as she's pro-choice.
It's not enough to actually win, the environment was just too toxic for Republicans, but it's enough to take away Obama's mandate in 2008.
Senator Barack Obama (D-IL)/Governor Kathleen Sebelius (D-KS) 50%
Secretary of State Condoleeza Rice (R-CA)/Former Governor Mitt Romney (R-MA) 48.75%