Found the problem. I had removed the old phone from the list of Lastpass approved mobiles. In spite of that, the Authenticator was working on my old phone, which seems like a bug to me. I did not notice that when I asked for a backup on the old phone, it told me that the backup failed (my mistake). So I re-enabled the old phone as an approved mobile using my pc, did the backup on the old phone, did the restore on the new phone, and it seems to work.