So I just setup a filedump running Debian Sarge 3.1 stable. I put up ssh, tested it from a few machines and it worked fine.

Then I disabled password authentication as I have a public RSA key that I use for servers that I have access to. It's used at school and for a couple of boxes at home as well. Never had any problems with it.

However, I always get this message:
Permission denied (publickey,keyboard-interactive).

It happens on my gentoo workstation as well as when I tried it from my Windows laptop with Putty. I can't enter the passphrase or anything.

Strangely enough, the same pair is setup with Cygwin under my Windows laptop, and it worked!

Why some and not the others? Any suggestions?

Anyone?

Make sure that the client's private key is permission x00 so no one else can read it. This is something that took me forever to figure out. SSH will not allow you to use key authentication (at least in my setup) when your private key file was readable by anyone but you. I would suggest 400 as once you create your private key, you really don't need or want any changes made to it.

Also do an ssh -v or -vv for verbose output.