The Android Mobile Authenticator App was updated recently (I assume the Windows / iPhone versions are either already updated or will soon be)

The great thing about this new version is you can write down your serial (not new) and a Restore Code (zomg new)

What this allows you to do is wipe the app and reinstall it, enter the serial and restore code, and your authenticator app will work for your account again without having to call blizzard to remove the authenticator. So if you get a new phone, just install the app and enter the info and you won't have to remove / re-add your authenticator.