I need to get passwordless SSH working between two red hat VMs. Here's the scenario:

On both VMs I have user bob. On VM1 as user bob I run ssh-keygen -t rsa. Then as user bob I run ssh-copy-id i bob@<ip of vm2>. I enter bobs password on vm2 and the public key is copied over to the authorized_keys file. I've verified that the key listed in the authorized keys file on vm2 is the same as the id_rsa.pub key on vm1. I've also verified that the permissions of bobs home, home/.ssh, home/.ssh/id_rsa, and home/.ssh/id_rsa.pub are correct.

Now I should be able to simply run the command 'ssh bob@<ip of vm2> and immediately get a terminal on vm2. Instead I'm still prompted for a password.

I've found that if I run these two commands on vm2 it will work:
(as root)
service sshd stop
/usr/sbin/sshd
(running 'service sshd start' does not work)

After running those two commands I can run the command 'ssh bob@<ip of vm2>' and get a terminal with no password required. What's going on here?

Is public key authentication enabled in sshd config?

well, it should, so have you looked at the msgs/logs in detail?
What version of RHEL is this, what VM tool eg Xen or KVM?

Main reason for ssh passwordless failure could be permission .Cross check whether you had enable wright permission for keys & .ssh file
Check the sshd_ config file you had whether enable authorized_ keys file path file & pubkey attentication yes in your sshd_ config file

Look after the link for passwordless login

http://www.linuxquestions.org/questi...os-rhel-35029/

Thanks for the help everyone. It turns out that there was an issue with the user's home directory. I had used puppet to create the users (does RHEL encrypt the home dir by default?). When I changed the location of the authorized_keys file to a different directory and point the sshd_config to that new directory everything worked fine.