Just to add my note on this event.
My cause of this problem was due to the account that was applied in the credential ring, while having permissions to the servers and WSUS, did not have permissions to the client machines and could not install the client sertificate.
I Configured another account that did have perms to the client machines and redistributed the cert.
To add another note:
With the recent KB2720211 patch and subsequent 1.73 patch for Patch Manager - you may want to check a few things:
1 - Under the Security and User Management - Server Certificates section - delete the old certificate that should have a revoked in the first part of the name
2 - Delete any saved Tasks where you had the Certificate deployed to a group of computers and re-create it (which will grab the new certificate).
In my case, there were a few unexplainable reasons why the client was getting that error until I performed both of those steps.
Thanks for adding this, super helpful for the community.
Additionally, I will add that it's much easier to deploy the new self-signed certificate via GPO than to use PM. Just make sure it's in both Trusted Root and Trusted Publishers of the target computer.