Time Machine says disk is full, but it was fine before! [duplicate]

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.