Time Machine couldn’t complete the backup

The past few days, I've been getting this error:

Time Machine couldn’t complete the backup to “TimeMachine3TB”.

The backup disk ran out of space unexpectedly. Time Machine will try to make more space available by removing expired backups during the next scheduled backup.

Open Time Machine preferences to select a larger backup disk or make the backup smaller by excluding files.

I have run Disk Utility and the "Verify Disk" and "Repair Disk". It found no problems with the drive. I have run it several times and still get the same error from Time Machine.

I'm fairly certain formatting the Time Machine partition on the drive would "fix" the problem, but it would leave m without a backup for a time period, as well as wipe all my past backups, so I'd like to avoid that "solution".

Has anyone run into this problem before or know how to solve it?