When you try and connect from machine A to machine B, do you get any kind of errors, or does it just fall back to the password prompt after it fails on the key?

Have you also tried specifying the key that you want to use when testing with the ssh client using the -i switch poited at your identity file?

What does the sshd_config file look like on the system you are trying to connect to? Perhaps it's not set to use auth keys?

UPDATE: Woops. Sorry, I didn't see the end there. So you are getting the password prompt. From the rest of the debug it does look like you are getting in with the key but then get prompted for auth again. I know this is really basic, but have you checked perms on your SSH server's .ssh/authorized_keys file to make certain they are mode 600? One final thing... have you tried openinging both your identity file on the client and the authorized_keys file in a text editor to verify that the key string is one line without returns at the end? That usually seems to be the most common cause of getting the password prompt with auth keys set up in my experience.