This literally happened to me and is the reason I no longer use Authenticator. Everything else on my entire phone restored, but not Authenticator.