Ssh – putty openssh rsa key signature invalid

I'm running a server with Debian Linux 3.2.46-1+deb7u1 with OpenSSH Server 6.0 and secured the login with a 2048 bit RSA key.

Although connecting with OpenSSH Client from another machine succeeds, the connection is refused when using Putty 0.63 on a Windows 7 machine with the following message:

Server refused public-key signature despite accepting key!

Because the problem applies only to Putty, I think all server configuration is correct. Putty works fine when running the server with Debian 2.6.32 and OpenSSH 5.5.

Here is the content of the auth.log:

matching key found: file /root/.ssh/authorized_keys, line 2
Oct  8 14:53:43 serverx sshd[28964]: Found matching RSA key: XX:XX
Oct  8 14:53:43 serverx sshd[28964]: debug1: restore_uid: 0/0
Oct  8 14:53:43 serverx sshd[28964]: debug3: mm_answer_keyallowed: key 0x7fb3828774c0 is allowed
Oct  8 14:53:43 serverx sshd[28964]: debug3: mm_request_send entering: type 22
Oct  8 14:53:43 serverx sshd[28964]: debug3: mm_key_verify entering [preauth]
Oct  8 14:53:43 serverx sshd[28964]: debug3: mm_request_send entering: type 23 [preauth]
Oct  8 14:53:43 serverx sshd[28964]: debug3: mm_key_verify: waiting for MONITOR_ANS_KEYVERIFY [preauth]
Oct  8 14:53:43 serverx sshd[28964]: debug3: mm_request_receive_expect entering: type 24 [preauth]
Oct  8 14:53:43 serverx sshd[28964]: debug3: mm_request_receive entering [preauth]
Oct  8 14:53:43 serverx sshd[28964]: debug3: mm_request_receive entering
Oct  8 14:53:43 serverx sshd[28964]: debug3: monitor_read: checking request 23
Oct  8 14:53:43 serverx sshd[28964]: error: hash mismatch
Oct  8 14:53:43 serverx sshd[28964]: debug1: ssh_rsa_verify: signature incorrect
Oct  8 14:53:43 serverx sshd[28964]: debug3: mm_answer_keyverify: key 0x7fb382871f80 signature unverified
Oct  8 14:53:43 serverx sshd[28964]: debug3: mm_request_send entering: type 24

After this happens, server switches to password auth and I'm able to login fine.

I already tried to clear Puttys known_hosts from the Windows Registry, whilst I think the error is about the public key for the private one, not the servers host key.

My question: Somebody out there who knows whats going wrong or what changed in OpenSSH from 5.5 to 6.0 could cause this? Any suggestions for a fix?