Earlier quoted context omitted.
Don't use SMS, use the Google Authenticator app. It's available on every mobile platform and implements open, RFC-specified OTP algorithms. And obviously works with Google's 2-factor implementation. Edit: forgot to mention, also open-source.
On Google's "Enter your code" screen, if you click the "Don't have your phone?" link, you get a pop-up that gives you the following options: * Use a backup code. Learn more * Send to your backup phone number ending in ## * I cannot access any of my phones Learn more I presume option #2 is the one cubicle67 is referring to. So yes, if someone gets my phone, they can then gain access to my Google account. Grrrrr...
I'm not trying to defend their stupid choice of offering option #2, but rather trying to offer a solution to your current problem.