I know this is not the answer you want, however if you switch between operating systems, iOS to Android or vise-versa, it is NOT possible to recover your backup in authenticator. The reason is because each OS uses a different storage platform for the backups and where to recover them from.
This is NOT an issue from Microsoft, but rather an issue from the device manufacturers and how their integration was developed for the Authenticator application.
Sorry to be the bearer of bad new, but you will have to resetup each code you had on the previous device.
Jason