"Time Machine must erase your existing backup history and start a new backup to correct this." Why is that?
“Has anyone seen this problem before?”
I have, and from what I have heard from reading forums over the years, it sounds like a very common problem with Time Machine: every once in awhile, it says “I need to delete your backup and start over.”
Or it says “I can’t backup because your backup device is full” (even though Time Machine is supposed to prune itself as needed).
Or something else comes up that causes Time Machine to choke.¹
Howard Oakley has cataloged a long list of issues with Time Machine, and even has some free apps to help work with Time Machine archives (unfortunately, nothing that can “repair” a “damaged” Time Machine backup, as far as I know).
In response to this I have developed the following attitude towards Time Machine:

Never rely on Time Machine as your only backup.

Use Time Machine to multiple locations (e.g. a Time Capsule or other remote Mac plus a local Mac) with the expectation that if one gets corrupted, you will still have the other one. Note that Point #1 still stands, even with Point #2

In addition to Time Machine, also use at least one (preferably two) of:



Backblaze
Carbon Copy Cloner
SuperDuper
Arq


¹ This is usually where someone will chime in and state that they have used Time Machine since it was first released and never had a problem with it. I do not doubt that there are some people who have had that experience, but I tend to consider them sort of like people who win the lottery: I am happy for them, but I would never expect to be one of them, and have decided to assume I never will be. YMMV.