Various forms of this error are printed in the PuTTY window, or written to the PuTTY Event Log (see section 3.1.3.1) when trying public-key authentication.
If you see one of these messages, it means that PuTTY has sent a public key to the server and offered to authenticate with it, and the server has refused to accept authentication. This usually means that the server is not configured to accept this key to authenticate this user.
This is almost certainly not a problem with PuTTY. If you see this type of message, the first thing you should do is check your server configuration carefully. Common errors include having the wrong permissions or ownership set on the public key or the user's home directory on the server. Also, read the PuTTY Event Log; the server may have sent diagnostic messages explaining exactly what problem it had with your setup.
Section 8.3 has some hints on server-side public key setup.