In my case I can see that the amount of space required by the backup grows while the backup is progressing. So initially it 'thinks' it only needs, say, 2GB, but that grows until, again say, 32GB. Then the error message is shown because the disk is full (it only has 32GB of free space, but requires more to complete the backup).
On initialisation it sees it can fit 2GB on the disk and performs no backup thinning because there is 32GB available. Then it starts the backup. The required backup space grows while progressing and when 32GB is reached the backup fails. This can be seen by clicking the small 'clock' icon at the top of the screen and holding the mouse there. The first 'entry' in the menu shows the amount backed up and the total backup size. Normally only the first number increases, in this case also the second number increases. Note that it can take a while before that starts happening.
When this happens I resolve it by creating a dummy file somewhere on the disk that is backed up (e.g. home directory). The required size of the file is unknown up front, so I start with the amount of space I know it requires at least, in the above example 32GB. If the backup still fails, use a larger size.
Compute the amount of Kb that go into 32GB: 1024x1024x32 = 33554432 (or use any other size).
Open terminal and type this command:
dd if=/dev/zero of=~/large_file bs=1024 count=33554432
This will take a while and create a 32GB file full of zeros in your home directory. Change the 'count' parameter to your required size.
Now start the backup again. It should first remove old backups (again, click the 'clock' icon and hold the mouse there).
When it is done removing old backups and starts backing up stop the backup (it will still fail!).
Delete the generated large file:
rm -f ~/large_file
Now restart the backup. If it still fails redo the process using a larger size until the backup succeeds.
Works for me!
