Possible Solution 1:
Using the puppet cert clean on the puppet master is the proper way. However since you're getting errors you may have a bad inventory of certificates.
Try doing a re-inventory then a clean:
$ puppet cert reinventory
$ puppet cert clean --all
Note: my example uses the --all flag, this will clear out all certificates, signed and unsigned. Also, be aware that the Puppet master should be stopped before running a reinventory.
Source: http://docs.puppetlabs.com/references/3.6.2/man/cert.html
Possible Solution 2:
$ puppet cert sign wrong.host.name
Notice: Signed certificate request for wrong.host.name
Notice: Removing file Puppet::SSL::CertificateRequest wrong.host.name at '/var/lib/puppet/ssl/ca/requests/wrong.host.name.pem'
$ puppet cert clean wrong.host.name
Notice: Revoked certificate with serial 87
Notice: Removing file Puppet::SSL::Certificate wrong.host.name at '/var/lib/puppet/ssl/ca/signed/wrong.host.name.pem'
Notice: Removing file Puppet::SSL::Certificate wrong.host.name at '/var/lib/puppet/ssl/certs/wrong.host.name.pem'
Possible Solution 3:
First: On Server
$ puppet cert --revoke wrong.host.name
$ puppet cert --clean wrong.host.name
Second: On Client
$ rm -rf /usr/lib/puppet/ssl
$ puppet agent --server [puppetmaster domain name] --waitforcert 60
Third: On Server (adjust as necessary)
$ puppet cert --list (you should see your host)
$ puppet cert --sign wrong.host.name
Also, double check that your client can reach your [puppetmaster domain name].
Source: https://serverfault.com/questions/574976/puppet-trying-to-configure-puppet-client-for-first-use-but-got-some-problems-wi