OK, having played around with this for quite a while I finally figured out the problem I was having.
If you always get asked for a password (even when the keys are found, match and correct passphrase entered) then try this! None of the above advice works for me...
This is for Ubuntu Breezy trying to SSH into Debian Etch, both fresh installs.
On Debian, as root, edit /etc/ssh/sshd_config and edit the line
StrictModes yesto read
Then, on Ubuntu, as a regular user run:
ssh-keygen -t rsaany then
ssh-copy-id -i ~/.ssh/id_rsa.pub you@debian
ssh you@debianto check it worked.
Simple really, but to find that StrictModes option took a lot of trial and error