[SOLVED] Can't get ssh key working Fedora 12

[meton_magis]

I have a problem that is driving me absolutely nuts.

I have a fedora 12 server that I use as a web proxy to encrypt my connections to the web. I have ssh running on port 443 ( a wifi I use blocks anything but 80 and 443 for some reason,) and open up a tunnel to port 3128 (squid) and send my firefox traffic through it. I have a couple friends I have setup for the same thing.

I am highly paranoid, and only allow authentication with a keypair. I've been using this setup on fedora 8, gentoo, fedora 11, and now fedora 12. I have used the same keys, copying them when I reinstall. I just reinstalled fedora 12 again (I had the same keys working on 12, I reinstalled to put in a bigger hard drive.) My keys work (I have one for putty on windows, and one for my linux desktop / laptop, both keys work fine.) I didn't need to change anything to get them working. However, my 2 friend's keys don't work. They get denied.
The error message displayed is "Permission denied (publickey)."

the /var/log/secure error is
"Feb 8 19:49:51 server1 sshd[3872]: Received disconnect from 256.256.256.256: 11: No supported authentication methods available"
(I changed IP address to bogus one.)
or will not have any error logged at all.

All home directories and files within have the same SELinux context, unconfined_u:object_r:user_home_dir_t:s0
and all ~/.ssh/authorized_keys have the same permissions. (and all parent directories.)

I have added nothing to TCP wrappers, and nothing to my iptables conf.

My sshd_config is

#########################################
# egrep -v '^\s*$|^\s*#' /etc/ssh/sshd_config

Protocol 2
SyslogFacility AUTHPRIV
PermitRootLogin no
MaxAuthTries 4

RSAAuthentication yes
PubkeyAuthentication yes
AuthorizedKeysFile .ssh/authorized_keys

PasswordAuthentication no
ChallengeResponseAuthentication no
GSSAPIAuthentication no
GSSAPICleanupCredentials yes
UsePAM yes
AcceptEnv LANG LC_CTYPE LC_NUMERIC LC_TIME LC_COLLATE LC_MONETARY LC_MESSAGES
AcceptEnv LC_PAPER LC_NAME LC_ADDRESS LC_TELEPHONE LC_MEASUREMENT
AcceptEnv LC_IDENTIFICATION LC_ALL LANGUAGE
AcceptEnv XMODIFIERS
X11Forwarding yes
Banner /etc/issue.net
Subsystem sftp /usr/libexec/openssh/sftp-server
#################################################

I have generated several new keys for those users, and can not get any of them to work. Both with putty-gen and with ssh-keygen. I can't login using `$ ssh localhost`on their ID's.

But my key works fine.

Does anyone have any idea why this won't work, or where I should be looking? This is driving me absolutely nuts.

Thanks

[meton_magis]

OK, nevermind. I don't know what I did, but it's working now. I didn't change anything, it just started working .......... I hate these kinds of solutions, I learned nothing from it, but it irritated me for 2 days ....