TL;DR: Google Authenticator doesn't backup on iOS; before erasing your old device, make sure to re-configure Google Authenticator on your new one.
I use the Google Authenticator app on iOS for 2-factor authentication into Google's services. Recently, I was transitioning to a new phone after giving my existing one to my mom for Christmas. I did the standard backup -> restore plan which put most of my settings on my new device without issues. Fortunately, before I erased the old device, I made sure all my apps worked, including the authenticator.
Apparently, the data the authenticator app stores is not backed up for whatever reason, which means that instead of being able to generate the keys needed to access my accounts, the authenticator was prompting me to set up a new account. The smart folks over here recommend taking a screenshot of the QR code Google's site gives you when you set up 2-factor authentication.
To Google: Why doesn't the authenticator back up its data? Seems this could be a nasty surprise for someone.
To Android users: Does this happen on Android as well?