You can't set up Authenticator again without turning on and off two-step verification. Imagine you were trying to authenticate a second phone -- you'd need your account password plus the code from Authenticator on your first phone. You couldn't do that if the first phone was missing (or got formatted), and as far as Google's concerned your freshly-wiped phone is now an entirely different phone. Allowing you to authenticate it again would be completely invalidating the security of the two-step process.

Edit: You can re-add the same phone by going to https://www.google.com/accounts/SmsAuthConfig and hitting the Edit link beside "Android" (the Mobile Application field). Oddly enough, this link didn't work for me in Chrome but it did in Internet Explorer.