Hey Schuyler,
That's weird! How many times did you try this?
This feature requires that you are backing up your data with your Google Account and that the app is using the backup service. After resetting your device, you'll need to re-enter the same information requested when you first set up your device. If you've been backing up your data to a Google Account, an option during the setup process allows you to restore it. So are you entering the same information at the beginning when setting it up, this could be why?
This is just a guess though.