Please read for an updated status on RailsCasts:
Learn more or hide this
GitHub User: themusicman
My guess is you are probably not using your id_rsa.pub key for the remote git repo. I had a different key set for a repo and got the same error. All I did was add my id_rsa.pub key to the remote git repo and everything worked fine. I think there is a way to also do ssh-add, but I was less than successful with getting that to work.
Use visudo and edit the sudoers file. Make sure the admin or sudo group, which ever your deploy user is in, has the NOPASSWD option:
%sudo ALL=(ALL) NOPASSWD:ALL