I run badblocks twice just to increase the entropy level and generated the key pair again, yet failed again. This was going from my Physical Box A to my VM Box B.
I then tried generating the key pair on Physical Box C and put the public key on Physical Box A. I then ssh from Physical Box C to Physical Box A and it worked fine. This proves my procedure was correct.
Unfortunately the original key pair generated on VM Box B was removed. Nevertheless, I did "ssh -vv username@<VM Box B>" from Physical Box A, and I saw the following at the end:
debug1: Next authentication method: publickey
debug1: Trying private key: /home/backup/.ssh/identity
debug1: Trying private key: /home/backup/.ssh/id_rsa
debug1: read PEM private key done: type RSA
debug2: we sent a publickey packet, wait for reply
debug1: Authentications that can continue: publickey,gssapi-with-mic,password
debug1: Trying private key: /home/backup/.ssh/id_dsa
debug2: we did not send a packet, disable method
debug1: Next authentication method: password
Is this hinting at something?