So I ran this on my server:
ssh -T git@bitbucket.org
And got "You can use git or hg to connect to Bitbucket. Shell access is disabled." It also said: "This deploy key has read access to the following repositories:" - listing the repository that I needed to clone.
And I would still get the "Permission denied" error when I tried to git clone the repository it said I have access to.