Hello @Diederik Janson ,
It seems you were running this AAD connect on a Domain Controller. Also the setup was done using automatic configuration and a custom service account was not used. It is generally advised to use a custom service account. The Default service account for ADsync Service when installed on a Domain controller is in the form on Domain\AAD_InstallationIdentifier . There is no way to recover the password for this account because its randomly generated.
In all probability , the current service account has lost its permission to access the database and hence you are facing this issue. The ADsync service encryption Keys probably would have gotten recreated and due to some permission issue you are getting the error. The Microsoft Azure AD sync service would need to be restarted by changing the service account to the original account before the upgrade. so you will need to go to the services console and update the <domain>\AAD_xxxxxxxxxx account again . I am not sure if it will automatically update the account with its password because the password for this account is created and rotated by domain controller itself but sometimes it will ask you to provide the password which you would not have and hence this operation will fail. If you try to go to Active Directory users and computers console and update this account's password and then use it to update the service account password on the ADsync service in services console, I think you will encounter error while starting the service again because the encryption keys created originally will be different and they could only be unlocked by old original password for AAD_xxxxx account which we will not have.
In my experience , I have seen reinstallation as the solution to this scenario most of the times. However you can try to open a support ticket with Microsoft and see if they are able to dig anything deeper to fix it . Should you have any issues opening a ticket , please let let us know by mailing on azcommunity[at]microsoft[dot]com with your azure subscription ID and tenant name referencing this thread and we will help you with alternate support options.
If you manage to solve this yourself, please do share your solution with the community. In case the information in this post is helpful , please do accept it as answer in the interest of the community.
Thank you.