Though having replaced two phones since using that solution - it can be a pain to have to re-set it up with each provider every time. I can see that if someone is prone to losing their phone, it will become a major issue.
I think the problem is that all the companies whom I use 2FA for have totally different methodologies for re-setting it up on a new device. Whilst some have an automated way of verifying my identity and resetting the new device almost instantly, I have had a couple that needed talking to a human support rep (inconvenient, but understandable) and one company that needed another employee in the company to do a full 2FA verification themselves, and then talk to a company support rep on my behalf to verify my request to reset my 2FA settings! (WTF).
Thus, each time I replace my phone, I find myself actually culling the number of services where I use 2FA purely because it was too much of a pain to go through the reset process, and it was actually easier to drop 2FA with them altogether (or in one case actually drop the service altogether).