There are several people posting the same issue.
To get Catalina to use the TC you might need to do a full reset and reconfigure it.
After a reset change to all very short names, with no spaces and pure alphanumeric.. not Apple recommended names which are hang over from Leopard or even earlier.
Passwords use the same rules.. but should be 8 characters min and any number you like above that.
Do the setup from the Catalina computer. If you still have issues you will need to do one more step.
There are a few changes that require very large amounts of disk space on the backup drive. To achieve this you need to start afresh. Before you erase the drive.. you should archive it to a USB Mac OS Extended Journaled disk plugged into the USB on TC. Of equal or greater size than the TC disk.
Once you have it archived.. about a day for the transfer. Then use a quick erase also on the disk tab of the airport utility and then you can start again with catalina. It should work ok now.
Note.. Time Machine is more and more buggy with every version of Mac OS. Since Sierra it has reached a point where I and many others here strongly recommend using alternative like Carbon Copy Cloner.