Try ssh -v or even -vv or -vvv to see what it thinks it's doing. I suspect it's either a different protocol version of ssh or the permissions of one of the files are wrong...
Then you don't have the files in the correct location(/home/username/.ssh/), or incorrectly named, or the wrong kind of file(Try making a DSA key instead), or incorrect ownership and/or permissions on ~/.ssh/ or the files themselves. ls -l ~/.ssh/
You are running ssh -v username@host, yes? not just -v.
I have been there.Please check the permissions on the directory ( probably home of user for whom you have generated keys) it has to be 700 and authorized_keys has to be 640.So if we are doing it for user xyz
Permissions "400" is enough for the authorized_keys file. Also important is the permissions on the .ssh directory itself, for which "100" would likely be enough.