I found out in my case, that the key file had comments at the beginning, which nova keypair-add didn't like. After removing the comments it worked.

I found that what fixed this for me was to create a new public key from the private key:

ssh-keygen -y -f private_key.pem > public_key.pub

I then used the newly generated key in the nova request, which worked just fine.

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.