I was having the same error under Windows using emacs 24.5.1 to connect to some company servers through /ssh:user@host. What solved my problem was setting the "tramp-default-method" variable to "plink" and whenever I connect to a server I ommit the ssh protocol. You need to have PuTTY's plink.exe installed for this to work.
Solution