So in order to prevent that attack vector, I need to make sure my phone isn't set up to receive calls to recover my account?

Thanks. I think I'll remove my phone number as a backup option.

Google periodically prompts me on login to add my cell phone number to increase my account's security.

I think someone confused about what "increase" means.

(And this is all the more surprising because in general I see all sorts of parts of Google making great end-user security decisions.)

It probably increases security for the average user, but decreases it for a targeted user.

Its not clear how they got his phone number though.

Phone book? Leaked address book? Leaked account database? Assume your phone number is public knowledge.

He said his gmail account was basically firstname lastname - given a name someone determined can generally make a fairly good guess as to phone number. Phone books, etc, etc.