There can be many reasons that would cause this error but one in particular is the need to convert it to openSSH format. After you've uploaded your public key execute this command:
# ssh-keygen -if public_key > authorized_keys2
Next move authorized_keys into your ~/.ssh directory. Chmod the file to 600.
# chmod 600 ~/.ssh/authorized_keys2
Make sure your .ssh directory has the proper permissions:
# chmod 600 ~/.ssh
Try it now. If you have further problems, try the steps on this site: How to set up SSH keys: Frustration with "Server refused our key"
You can learn how to generate SSH keys from Linux to Linux here (by Tor).