From the troubleshooting guide:
Permission denied (publickey)
This is usually caused when ssh cannot
find your keys. Make sure your key is
in the default location, ~/.ssh. If
you run ssh-keygen again and just
press enter at all 3 prompts it will
be placed here automatically. Then you
can add the contents of id_rsa.pub to
my github keys. If id_rsa.pub doesn’t
work try id_dsa.pub. You might need to
generate a new dsa key with ssh-keygen
-t dsa if you just have an rsa key.
If you are still having problems and
none of the above worked, you may have
a blacklisted key from a debian
open-ssh bug. you should update
open-ssh and re-generate your keys.
So, just to check - are your keys available under ~/.ssh/ as id_rsa and id_rsa.pub or otherwise, are you specifying their use?