This issue is fairly common and there are plenty of articles and guides on how to debug this particular problem.
Most often the issue with this error is that either the certificates in use are not correctly setup either at the ldap.conf or within the Active Directory store.
But, I recently dealt with an issue that took me down a rabbit hole that I would never have expected.
While debugging this error from within a web app I had checked all of the common issues and everything should have been working without issue, but it was still failing with the unwilling to perform error.
The actual fault was that the RID Master FMSO role was on a un-contactable server for the domain and the domain controller that was left in the directory had ran out of the allocated SID from when the RID master was last contactable, this was causing the error when trying to create a new account.
The fix to the was fairly simple, seize the role, clean up the dead server details in sites and services and all was good.
Moral of this story, be confident in the setup, if you are sure the certificates and permissions for the user being used, run dcdiag on your target domain controller and check for errors specially around the roles and replication.