I recently ran into an issue after upgrading my gems in which capistrano would fail during the SSH known_hosts verification. I’m on OS X with capistrano 1.4.1, net-ssh 1.1.0 and can manually SSH to the deploy machine. A little googling turned up an easy work around for the problem. Simply add the following line to your deploy.rb and capistrano will skip the known_hosts verification.
ssh_options[:paranoid] = false |


well, you should probably leave paranoid on and verify host keys to make sure you aren’t being attacked. alternately, you can just remove the host entry in ~/.ssh/known_hosts, shell back in, accept the (presumably) new fingerprint and it will likely go away.
the known_hosts file is there for a reason, to verify that the host you are sending your credentials to is the host you think it is.
MML.. i did exactly as you tried and it was still throwing errors. The only kink was I was deploying from my linux server to the same linux server. Maybe it was confused over the 127.0.0.1 or something.
It worked fine from another server without the paranoid flag. But with the paranoid flag, it works from both.
I ran into this recently. Deleting old known_hosts entries pertaining to the hosts I was attempting to deploy to solved the matter for me.
Sounds like Jamis is aware of this problem but is not having it himself.
Whatever capistrano uses to make ssh connections, it doesn’t seem to respect the .ssh/config settings at all. This is Really Bad, because it creates a situation (that I commonly encounter) where cap commands fail due to ssh issues (host verification, bad username, etc) but ssh to the host works fine.