AWS EC2 Ubuntu & BitBucket connection error

I've set up an AWS EC2 Ubuntu 14 instance and everything working fine. I am now trying to connect it to BitBucket with private/public key but that seems to be a very painful process from some reason.

I have a public/private key in my ~/.ssh folder named bitbucket_rsa & bitbucket_rsa.pub. I copied bitbucket_rsa.pub content to BitBucket ssh keys and it accepted it.

When checking the connection via ssh -T hg@bitbucket.org I get the following message which seems to be ok (by searching online):

logged in as [...].
You can use git or hg to connect to Bitbucket. Shell access is disabled.

However, when trying to do a git clone via:

sudo git clone git@bitbucket.org:myusername/testrepo.git

I get the following message

Permission denied (publickey).
fatal: Could not read from remote repository.
Please make sure you have the correct access rights
and the repository exists.

I can't for the life of me understand what is going on. Spent way too much time on this than I should already and not getting any progress. I was thinking it might be related to the public key being copied wrong (manually copy pasted it since xclip and xsel did not work (error could not open display) but since the connection test works fine, I am now thinking it is something else.

Help would be greatly appreciated.