The certificate retrieved from the master does not match the agent's private key.

While implementing puppet in our environment, I got into this issue with newly created machine. Running 'puppet agent -t' for the first time:

First you must make sure the certname in puppet.conf matches the hostname of the machine, but the commands mentioned above may still not work and result in the same error.

After a little digging on the puppet master machine, I found the following domain.com.pem file in the following path:

/var/lib/puppet/ssl/ca/signed

Just remove this agent's pem file, and redo the commands again. Fixed the issue for me.

Edit: Also ensure you are working under root in puppet master :P