If I were him, I'd pick Utah Gov. Jon Huntsman, Jr, forty-four years old, and has a famous family name (at least in his state).
If the Huntsmans are only known in Utah, then why would name recognition be relevant here? None of the Republicans need any help to win Utah.
If a Mormon cannot win the presidency outright, then it might help to get the country accustomed to seeing a Mormon as VP before they let go their inhibitions about having a Mormon as President of the United States.
Why would McCain care about any of that?