I was getting this error message while trying to connect to my EC2 instance using this plugin. I knew the username and private key were correct and after some investigation, I realized I had port 22 locked down to just my IP address. If you use your domain (i.e. http://www.example.com) EC2 will route the call through your security groups and block the port. Change your host to localhost and the routing stays local. Fixed the problem for me.
http://wordpress.org/extend/plugins/ssh-sftp-updater-support/
