I think Condoleeza Rice would be a good choice, to give the ticket some foreign policy credentials.
One of the main architects of GWB's disaster in foreign relations? WTF LOL...
Nikki Haley? Young, charismatic, a minority. She's said she wouldn't do it, but the cardinal rule of running for Vice President is to act like you're not running for VP.
She's a damaged good after failing miserably to deliver SC to Mitt during primaries.
If Romney wants a Governor, relatively fresh in national politics, still popular in home state and, most importantly, not an idiot like Sarah Palin, then Martinez is an obvious answer.