Every couple of days I plug a 4TB drive into my MacBook Pro and use Time Machine to run a backup. Over recent weeks though it's failed repeatedly somewhere in the process.
Today I gave in and reluctantly erased the drive to start fresh.
After an hour or so: 30% backed up, so far.

I’ve had the exact same problem and solved it the same way too. Thankfully, it does seem to work.

@gregmoore Yes, I woke this morning to a set of fresh backups. Hooray!