Cannot Clone Repository

Getting this error:
Initialized empty Git repository in /directory/path/.git/
Permission denied (publickey).
fatal: The remote end hung up unexpectedly

• I've changed the key like 10 times.
• Removed my config file to test and still same error.
• Moved my keys to another folder outside my home directory and update the config file but still same error.
• I added file to the repository as well and still same error.
• I've been able to clone repositories on a mac and centos server just fine. But the OS I'm having issues with is Ubuntu Server 10.04 LTS.

I was able to use the same key to clone a repository from GitHub just fine, so the fact that it works with them and not with you confuses me. I really want to start use your service. So please, any help would be much appreciate.