Cannot enable Time Machine encrypted backups since updating to Catalina
It seems like the issue was that Time Machine -dialog itself didn't have correct admin rights, but wasn't showing the padlock for unlocking them. Opening Time Machine from System preferences instead of the upper bar seemed to help, and that's how I was able to click the padlock and give enough rights for Time Machine to write into System Keychain.