Description of problem:
I was using OpenSSH with public key authentication since FC3.
Keys were generated by ssh-keygen and converted to Putty in 2002.

After upgrade to FC10 i was no longer able to connect via Putty to my FC10 box using public key:

Using username "xxxxxx".
Server refused our key
xxxxx@xxxx's password:

I have tried to regenerate the keys - still the same result.

Version-Release number of selected component (if applicable):
openssh-5.1p1-3.fc10.i386

How reproducible:

Steps to Reproduce:
1. Setup public key auth in Putty.
2. Setup authorized_keys2
3. Try to connect
  
Actual results:

Server refused our key


Expected results:

Successfull auth.

Additional info:

SSHD debug mode works perfectly!
No errors:

usr/sbin/sshd -d

debug1: sshd version OpenSSH_5.1p1
debug1: read PEM private key done: type RSA
debug1: private host key: #0 type 1 RSA
debug1: read PEM private key done: type DSA
debug1: private host key: #1 type 2 DSA
debug1: rexec_argv[0]='/usr/sbin/sshd'
debug1: rexec_argv[1]='-d'
debug1: Bind to port 22 on 0.0.0.0.
Server listening on 0.0.0.0 port 22.
debug1: Bind to port 22 on ::.
Server listening on :: port 22.
debug1: Server will not fork when running in debugging mode.
debug1: rexec start in 5 out 5 newsock 5 pipe -1 sock 8
debug1: inetd sockets after dupping: 3, 3
Connection from 192.168.1.100 port 2002
debug1: Client protocol version 2.0; client software version PuTTY_Release_0.60
debug1: no match: PuTTY_Release_0.60
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_5.1
debug1: permanently_set_uid: 74/74
debug1: list_hostkey_types: ssh-rsa,ssh-dss
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: client->server aes256-ctr hmac-sha1 none
debug1: kex: server->client aes256-ctr hmac-sha1 none
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST_OLD received
debug1: SSH2_MSG_KEX_DH_GEX_GROUP sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_INIT
debug1: SSH2_MSG_KEX_DH_GEX_REPLY sent
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: KEX done
debug1: userauth-request for user dusha service ssh-connection method none
debug1: attempt 0 failures 0
debug1: PAM: initializing for "dusha"
debug1: userauth-request for user dusha service ssh-connection method publickey
debug1: attempt 1 failures 0
debug1: test whether pkalg/pkblob are acceptable
debug1: PAM: setting PAM_RHOST to "home-dusha"
debug1: PAM: setting PAM_TTY to "ssh"
debug1: temporarily_use_uid: 500/500 (e=0/0)
debug1: trying public key file /home/dusha/.ssh/authorized_keys
debug1: fd 4 clearing O_NONBLOCK
debug1: restore_uid: 0/0
debug1: temporarily_use_uid: 500/500 (e=0/0)
debug1: trying public key file /home/dusha/.ssh/authorized_keys2
debug1: fd 4 clearing O_NONBLOCK
debug1: matching key found: file /home/dusha/.ssh/authorized_keys2, line 1
Found matching DSA key: 2f:0f:ba:5f:89:03:a4:3c:02:1c:e3:7c:b1:4a:d6:fa
debug1: restore_uid: 0/0
Postponed publickey for dusha from 192.168.1.100 port 2002 ssh2
debug1: userauth-request for user dusha service ssh-connection method publickey
debug1: attempt 2 failures 0
debug1: temporarily_use_uid: 500/500 (e=0/0)
debug1: trying public key file /home/dusha/.ssh/authorized_keys
debug1: fd 4 clearing O_NONBLOCK
debug1: restore_uid: 0/0
debug1: temporarily_use_uid: 500/500 (e=0/0)
debug1: trying public key file /home/dusha/.ssh/authorized_keys2
debug1: fd 4 clearing O_NONBLOCK
debug1: matching key found: file /home/dusha/.ssh/authorized_keys2, line 1
Found matching DSA key: 2f:0f:ba:5f:89:03:a4:3c:02:1c:e3:7c:b1:4a:d6:fa
debug1: restore_uid: 0/0
debug1: ssh_dss_verify: signature correct
debug1: do_pam_account: called
Accepted publickey for dusha from 192.168.1.100 port 2002 ssh2
debug1: monitor_child_preauth: dusha has been authenticated by privileged process
debug1: temporarily_use_uid: 500/500 (e=0/0)
debug1: ssh_gssapi_storecreds: Not a GSSAPI mechanism
debug1: restore_uid: 0/0
debug1: SELinux support enabled
debug1: PAM: establishing credentials
PAM: pam_open_session(): Authentication failure
debug1: PAM: establishing credentials
debug1: permanently_set_uid: 500/500
debug1: Entering interactive session for SSH2.
debug1: server_init_dispatch_20
debug1: server_input_channel_open: ctype session rchan 256 win 16384 max 16384
debug1: input_session_request
debug1: channel 0: new [server-session]
debug1: session_new: session 0
debug1: session_open: channel 0
debug1: session_open: session 0: link with channel 0
debug1: server_input_channel_open: confirm session
User child is on pid 14209
debug1: server_input_channel_req: channel 0 request pty-req reply 1
debug1: session_by_channel: session 0 channel 0
debug1: session_input_channel_req: session 0 req pty-req
debug1: Allocating pty.
debug1: session_new: session 0
ssh_selinux_setup_pty: security_compute_relabel: Invalid argument
debug1: session_pty_req: session 0 alloc /dev/pts/2
debug1: server_input_channel_req: channel 0 request shell reply 1
debug1: session_by_channel: session 0 channel 0
debug1: session_input_channel_req: session 0 req shell
debug1: Setting controlling tty using TIOCSCTTY.
debug1: Received SIGCHLD.
debug1: session_by_pid: pid 14210
debug1: session_exit_message: session 0 channel 0 pid 14210
debug1: session_exit_message: release channel 0
debug1: session_by_tty: session 0 tty /dev/pts/2
debug1: session_pty_cleanup: session 0 release /dev/pts/2
debug1: session_by_channel: session 0 channel 0
debug1: session_close_by_channel: channel 0 child 0
debug1: session_close: session 0 pid 0
debug1: channel 0: free: server-session, nchannels 1
Connection closed by 192.168.1.100
debug1: do_cleanup
Transferred: sent 3640, received 3272 bytes
Closing connection to 192.168.1.100 port 2002
debug1: PAM: cleanup
debug1: PAM: deleting credentials

BUT WHEN I start SSHD service in normal mode - I  - key refused error and I have to type in my password.

/etc/ssh/sshd_config:

#       $OpenBSD: sshd_config,v 1.80 2008/07/02 02:24:18 djm Exp $

# This is the sshd server system-wide configuration file.  See
# sshd_config(5) for more information.

# This sshd was compiled with PATH=/usr/local/bin:/bin:/usr/bin

# The strategy used for options in the default sshd_config shipped with
# OpenSSH is to specify options with their default value where
# possible, but leave them commented.  Uncommented options change a
# default value.

Port 22
#AddressFamily any
#ListenAddress 0.0.0.0
#ListenAddress ::

# Disable legacy (protocol version 1) support in the server for new
# installations. In future the default will change to require explicit
# activation of protocol 1
Protocol 2

# HostKey for protocol version 1
#HostKey /etc/ssh/ssh_host_key
# HostKeys for protocol version 2
#HostKey /etc/ssh/ssh_host_rsa_key
#HostKey /etc/ssh/ssh_host_dsa_key

# Lifetime and size of ephemeral version 1 server key
#KeyRegenerationInterval 1h
#ServerKeyBits 1024

# Logging
# obsoletes QuietMode and FascistLogging
#SyslogFacility AUTH
SyslogFacility AUTHPRIV
#LogLevel INFO

# Authentication:

#LoginGraceTime 2m
#PermitRootLogin yes
#StrictModes yes
#MaxAuthTries 6
#MaxSessions 10
RSAAuthentication yes
PubkeyAuthentication yes
#AuthorizedKeysFile     .ssh/authorized_keys

# For this to work you will also need host keys in /etc/ssh/ssh_known_hosts
#RhostsRSAAuthentication no
# similar for protocol version 2
#HostbasedAuthentication no
# Change to yes if you don't trust ~/.ssh/known_hosts for
# RhostsRSAAuthentication and HostbasedAuthentication
# IgnoreUserKnownHosts yes
# Don't read the user's ~/.rhosts and ~/.shosts files
#IgnoreRhosts yes

# To disable tunneled clear text passwords, change to no here!
#PasswordAuthentication yes
#PermitEmptyPasswords no
PasswordAuthentication yes

# Change to no to disable s/key passwords
#ChallengeResponseAuthentication yes
ChallengeResponseAuthentication no
# Kerberos options
#KerberosAuthentication no
#KerberosOrLocalPasswd yes
#KerberosTicketCleanup yes
#KerberosGetAFSToken no

# GSSAPI options
#GSSAPIAuthentication no
GSSAPIAuthentication yes
#GSSAPICleanupCredentials yes
GSSAPICleanupCredentials yes

# Set this to 'yes' to enable PAM authentication, account processing,
# and session processing. If this is enabled, PAM authentication will
# be allowed through the ChallengeResponseAuthentication and
# PasswordAuthentication.  Depending on your PAM configuration,
# PAM authentication via ChallengeResponseAuthentication may bypass
# the setting of "PermitRootLogin without-password".
# If you just want the PAM account and session checks to run without
# PAM authentication, then enable this but set PasswordAuthentication
# and ChallengeResponseAuthentication to 'no'.
#UsePAM no
UsePAM yes

# Accept locale-related environment variables
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

#AllowAgentForwarding yes
#AllowTcpForwarding yes
#GatewayPorts no
#X11Forwarding no
X11Forwarding yes
#X11DisplayOffset 10
#X11UseLocalhost yes
#PrintMotd yes
#PrintLastLog yes
#TCPKeepAlive yes
#UseLogin no
#UsePrivilegeSeparation yes
#PermitUserEnvironment no
#Compression delayed
#ClientAliveInterval 0
#ClientAliveCountMax 3
#ShowPatchLevel no
#UseDNS yes
#PidFile /var/run/sshd.pid
#MaxStartups 10
#PermitTunnel no
#ChrootDirectory none

# no default banner path
#Banner none

# override default of no subsystems
Subsystem       sftp    /usr/libexec/openssh/sftp-server

# Example of overriding settings on a per-user basis
#Match User anoncvs
#       X11Forwarding no
#       AllowTcpForwarding no
#       ForceCommand cvs server


All permissions on /.ssh/* are OK
As I have already mentioned - this setup was working without problems since 2002 on FC3, FC5, FC7, FC8, FC9