I came across with this error "Command execution failed: Error Constructing or Publishing Certificate" when requesting certificate from internal CA server for Lync server 2013 running on windows server 2012.
After digging into the issue and the error I found that I will have to restart the Active Directory Certificate Services on CA server. Looked into application log and found the event id 53.
I checked and found that Active Directory Certificate Services service on CA server service is already running.
Now I just had to restart this services and after restarting the services, request the certificates again from Lync server and it will complete successfully.
Cheers,