[rzs0502]

My keys work with the following version:
openssh.base.server 4.3.0.5301 COMMITTED Open Secure Shell Server

Common problems are
Group write permission on the particular user's home directory
Key entry in authorized_keys is not on a single line (usually when copied & pasted)
~/.ssh directory and it's contents having group/world write permissions

If all else fails, use a couple of '-v' flags on the ssh command to see if anything useful is logged.

Hope it helps.