I had the permissions right on all the files, on both the client and the server, yes, I checked this, and that.
So, here I am racking my brain, "why isn't this working", darn it.. what am I overlooking? So I IM'ed a friend of mine, Richard Harman, who is the master of a bunch of things, one of the things is Linuxy, Unixy stuff -- at this point I'm at my wits end, and trying to figure it out, I am racking my brain.
Richard connects up to my computer, and he has the same problem (can't connect via SSH key), so it's obviously a server problem.
We start daemons in debug mode, looking at RPM packages (this particular server was running Fedora 10), heck, I was even looking at bugs in SELINUX as the culprit. Nothing.
We noticed one line in particular that was bothering us.. every time someone tried to connect to sshd on the SERVER's SSHD debug line, it was trying to access /root/.ssh/authorized_keys. No matter what the user. Obviously, this isn't right. I tested this out by moving my authorized_keys file to root's /.ssh directory and it worked right away.
After poking around a bit, Richard found the problem:
Because, when SSHD starts up, the sshd_config file was expanding "~/" to the home directory, and since sshd starts as root.. the ONLY directory it was going to look in was /root/.ssh/authorized_keys
Richard changed this to:
It worked and life is fine now. Two characters. TWO. (That I didn't put there, or at least don't remember putting there.)