Why does Déjà Dup say there is no space left?

So there are three possible places where Deja Dup might be out of space, and I don't think its error message tells you which. There is a bug filed about that.

• You may have run out of space on the target partition (which it sounds like you didn't)
• You may have run out of space in your home directory (~/.cache/deja-dup can get large)
• You may have run out of space in /tmp

You can move the location of the cache-directory as follows (create a symlink to a new cache location)

mkdir /othervolume/.deja-dup-cache
mv ~/.cache/deja-dup/* /othervolume/.deja-dup-cache/
rmdir ~/.cache/deja-dup
ln -sf /othervolume/.deja-dup-cache ~/.cache/deja-dup

to change the location of the tmp-directory have a look at the following post: Deja Dup backup, change use of /tmp to another folder/location