Catalina: Time Machine claims there is not enough space for a backup
I had a similar issue where TimeMachine was complaining about not being able to backup to a USB attached external disk. (Even though there was plenty of space for the backup).

Apparently the connection was in an unexpected error state, so I did the following and all was working afterwards:


Shutdown the Mac
Unplugged the External HD
Unplugged the USB cable
Waited 60 seconds


Then plugged them back in and restarted the Mac.

All was good again.  (Hope this works for you too.)