I believe the following part is what is overwriting your validating key with something else.
I followed all the steps of the tutorial including cloning the git repo and especially these particular steps:
cp ~/chef-repo/.chef/knife.rb ~/nagios-quick-start/.chef
cp ~/chef-repo/.chef/USERNAME.pem ~/nagios-quick-start/.chef
cp ~/chef-repo/.chef/validation.pem ~/nagios-quick-start/.chef
When you run knife ec2 server create, it will
1. launch a new ec2 instance
2. install chef on this instance
3. bootstrap it. it will automatically copy the correct validation.pem key while this happens.
Can you remove the validation.pem from ~/nagios-quick-start/.chef and try. Alternately, you could copy /etc/chef/validation.pem there.
Also, can you make sure that if you are using a AMI to launch instnace, it does not have stale /etc/chef/validation.pem on it.
Founder and Principal Consultant