Software :: Sftp Works But Ssh Does Not / What To Do?

I see a bunch of threads that deal with ssh working but sftp not. I just the opposite of that. When I use sftp I'm immediately prompted for the key's passprhase and all works well. When I use ssh I am told

Permission denied (publickey).

I've looked at the file and I have read and write permission. I can use sftp, so it's not a problem on the other end. I can access the same server with the same computer using a different user account and a different key. I can access the same server using the same key from a different computer.

I'm using Ubuntu 10.10 with OpenSSH 5.3