Here's the issue
Kelly Ayotte - Too inexperienced (had only been in the Senate for 1.5 years); too similar to Romney
Chris Christie - Too inexperienced (had only been Governor for 2.5 years); too brash; would upstage Romney
John Cornyn - Senate leadership; boring white guy
Mitch Daniels - Boring white guy; had job at Purdue lined up; probably would have declined for same reasons he didn't run for President
Bill Frist - Boring white guy; out of Senate for too long; doing other things and probably wouldn't have been interested
Mike Huckabee - Boring white guy; too socially conservative; too controversial; wrapped up in other pursuits
Bob McDonnell - Corrupt
Tim Pawlenty - Incredibly bland; no advantages that Ryan doesn't bring
Rob Portman - Endorsed SSM and would have done so even had Romney not picked him; boring white guy; bland
Marco Rubio - Too inexperienced (had only been in the Senate for 1.5 years); would not have performed well on national stage
...and Paul Ryan. The best choice? Certainly was never realistically going to deliver Wisconsin or beat Biden in the debate, would repel older voters due to Medicare and the Ryan budget, and had unfortunate ties to the House leadership, but was also young, handsome, solidly conservative without being a scary firebreather, wonkish, and reasonably accomplished
Romney really didn't have any good choices.
Although very bland, Pawlenty may have made a difference in Iowa and Minnesota, Cornyn would have made Romney stronger in the South