Have a look in nova-api.log, there maybe more specific error details. Nova-api runs ssh-keygen -q -l -f id_rsa.pub to get the fingerprint. I guess this command will work on the host where the keypair was created - can you add the output to the question. But for some reason it is not working of the host running nova-api. Maybe they have different versions of ssh.