First, you need to generate a new SSH key. Use ssh-keygen in your terminal. Call it beanstalk or whatever suites you.
Copy your new key:
pbcopy < beanstalk.pub
Go to beanstalkapp.com, login to your account and go to profile settings:
Click Add public key and paster clipboard contents into text input.
Start your client and go to account settings. Configure it like that:
Finally go to the problematic repository.
Don’t close error message!
Click Edit connection settings and change repository URL to the one copied from beanstalkapp website repo summary:
And voilà! It should work.