Cannot enable Time Machine encrypted backups since updating to Catalina

I updated to Catalina recently and previously I was able to backup my MacBook using Time machine backups. After the update time machine backup failed because of empty password issue (don't remember full error message), and now when I try to enable backups I'm getting following error after entering the backup password:

An error occurred while creating a System Keychain entry for encrypted Time Machine network backups
You can try using the Keychain Access utility to edit the System Keychain.

Any suggestions how to fix this?

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.