If you've never ssh'd into a host before and you begin deploying with fezzik to that host, you will get a confirmation message asking you to add it to the list of known hosts. Since fezzik isn't accepting keyboard input, the deploy hangs there.
Here's a reference for implementing workaround:
http://www.sharms.org/blog/2009/01/mass-adding-hosts-to-ssh-known_hosts-file/
One thing that's unclear about this addition is how "optionally" should be implemented in fezzik. Maybe an "add hosts to deploy target" global option in deploy.rb?