Have you tried logging in as the jenkins user?
Try this:
sudo -i -u jenkins #For RedHat you might have to do 'su' instead.
git clone [email protected]:your/repo.git
Often times you see failure if the host has not been added or authorized (hence I always manually login as hudson/jenkins for the first connection to github/bitbucket) but that link you included supposedly fixes that.
If the above doesn't work try recopying the key. Make sure its the pub key (ie id_rsa.pub). Maybe you missed some characters?