We have opened a Case # 01857236.
We have a workaround, that is changing all backup jobs to use the local machine administrator for each VM we have been able to run backups.
It is not something I would like to have as a permanent solution. Before the upgrade, most of our backup jobs used the same domain account.
Also, I would like to understand what happened and why. Microsoft is fiddling with his crystallographic algorithms to remove older ciphers and I fear problems coming from that direction.