Time Machine says disk is full, but it was fine before! I have a 4TB external Time Machine disk. There are three internal volumes totaling 3.3TB that have been actively backed up to that external drive for a few weeks. 

I was troubleshooting something and moving a bunch of files around, so I briefly turned off Time Machine. When I turned it back on, it started backing up... but then it stopped later, saying "there is only 707MB available on the drive, but 3.3GB is required." 

It's almost as if it refuses to overwrite the old backups. It wants to start an entirely new backup or something. How can I make it pick up where it left off without having to delete that entire backup and start anew? I don't like deleting backups!
Since you state that you have three internal volumes, I am going to assume that when you were:


  "troubleshooting something and moving a bunch of files around"


that you moved files between volumes. Time Machine will want to make a backup copy of a duplicate file that is moved/copied to a different volume. It isn't smart enough to notice that it already has a backup copy of the file(s) when they existed on another volume.

It's possible that if you moved a bunch of stuff around while Time Machine was off that it is having trouble reconciling all the changes and it's being compounded by disk drives that are on the full size (as stated before, I agree with the 20% free space threshold.)

Excluding some files from the Time Machine options or using the Time Machine app to delete some old files might help.
This is quoted from http://support.apple.com/kb/HT1427


  You can also enter the Time Machine restore interface and find files that can be removed from the backup drive itself to conserve space. To do this, select the file(s) and from the Action pop-up menu (gear icon) in the Time Machine Finder window choose "Delete All Backups of...". Be sure to only delete files you are sure you won't need or want to restore later.