"the disk that your backup is saved on doesn't have enough free space."
If you were trying to back up something into the recovery partition, you would receive this type of message.
In this case it is better to just shoot the messenger. There is no problem with having a full recovery partition, it has a set amount of space and the files are protected. If the message continues to pop-up, you just need to disable it.
Windows would apply the same message, if you were using too small of a USB flashdrive, and trying to back up there.