I've been dealing with this exact same issue since February 2022. It just flat out stopped working one day. After countless emails with customer support, and going through every type of troubleshooting step and I continue to end up with the same result.
Last night, October 4, I finally got my new phone, and could go through supports latest effort. Remove all MFA, disable the app in my account, and delete the app. Once it was fully deleted, download the LATEST version (which I always had) and go through the setup and verification all over again.
I had to go through each and every account (26 total accounts) that I had MFA setup on, and remove it from the Authenticator to do all their troubleshooting, only to have it give me my favorite error message;
Backup failed. Please check your internet connection and try again.
I've lost track of how many times I was asked to remove the Authenticator from my account and then re-enable it. I've been asked to send dozens of screenshots, video screen captures, all to end up at the exact same outcome.
Here's what I know for certain after all the customer support and troubleshooting I've been through in nearly 10 months;
- It's not my device, as I've tried on my iPad, and on a brand new phone.
- It's not my cellular service, because I tried doing this on another carrier.
- It's not the WiFi I'm connected to, because it's been attempted on dozens and dozens of different networks.
- It's not the location I'm in, as I've tried it at home, work, and while on vacation in a different state and time zone.
The problem lies either with SOMETHING in my account, or with LastPass and the Authenticator itself. I'm just finally glad that I'm not alone, and that other people are, granted UNFORTUNATELY, going through the exact same problem.
The customer service has been less than garbage throughout the entire ordeal. A week or more will easily go by without hearing anything from anyone. A couple times, I even received an email saying they were considering the matter closed, until I would reply back stating nothing had been resolved and the case wasn't to be closed.
I'm a user since 2018, and a paying customer for going on 2 years. The first year had zero issues, but year 2 has been abysmal. My renewal is in February, and if this problem isn't fixed soon, I'll be exporting all of my passwords/credentials and finding another password service to use. And if I'm being honest, I've hung in waaaaaaaay too long, anyone else would have likely just switched. I don't want to go through the process again, but I'm starting to warm up to the idea.
