I can and have reinstalled authenticator (I could reinstall on another phone but what would be the purpose?).
I use Googles authenticator app
http://goo.gl/Jyr3YKIt got uninstalled when I sent my phone off to be fixed and they factory reset it... (but, to best of my knowledge, large OS updates, uninstall many apps and then re-install them automatically as part of the upgrade process, it is a known problem with (some/this) authenticator that it doesn't save the accounts (hence the need for authy?)... I didn't know this at the time... I was not aware of any benefits to using authy, never crossed my mind that un-installing and then re-installing the authenticator app would cause this issue... Josef27, seems silly to need a third partry app to make a security app functional in real world situations?)
http://goo.gl/YUORtK others are having similar issues, sadly the link they supply to googles specific issue is a dead link.
The authenticator does not appear to save accounts. (This whole authentication process is still new to me, so I am finding these problems as they arrive).
To add an account to the authenticator it requires a special code, to get that code I need access to my account... catch 22