Upon recommendation from a few people, I decided to give CyanogenMod another shot. I've been sticking to AOSP and the "Google Experience" (didn't have much luck with AOSP), because for the most part since ICS I just preferred the vanilla experience and there were always precious few bugs with the stock ROMs.
Of course I'm running nightlies of CM, so there are some problems to be expected - but I want the new stuff. So I backed up the phone, while proceeding to download the latest nightly for maguro, including paying special attention to back up my Google Authenticator.
Installed CM and the Google Apps, started setting everything up and went to restore backups for Authenticator when disaster struck - the back ups are empty. Whoops! Fortunately I only really use it for Google and for Blockchain.info. Blockchain.info is backed up to paper wallets, so I just created a new one and imported everything back in. I can get back into Google via SMS code backup, so that's okay too - but it was rather stressful trying to work out why restoring the backup didn't work.
I'm still very curious as to why the backup for authenticator failed - clearly the data for my other apps is still there. I also have a nandroid backup from a few months back that will no doubt include the data I want, but I've yet to spend time working out how to extract from it.