Cuando uso el comando ssh para conectarme manualmente al host, todo funciona bien:

$ ssh -v [email protected] -p 10000
OpenSSH_6.1p1, OpenSSL 1.0.1c 10 May 2012
debug1: Reading configuration data /home/todd/.ssh/config
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: Connecting to mycli.abc.com [mycli.abc.com] port 10000.
debug1: Connection established.
debug1: identity file /home/todd/.ssh/id_rsa type 1
debug1: identity file /home/todd/.ssh/id_rsa-cert type -1
debug1: identity file /home/todd/.ssh/id_dsa type -1
debug1: identity file /home/todd/.ssh/id_dsa-cert type -1
debug1: identity file /home/todd/.ssh/id_ecdsa type -1
debug1: identity file /home/todd/.ssh/id_ecdsa-cert type -1
debug1: Remote protocol version 2.0, remote software version SSHD-CORE-0.6.0
debug1: no match: SSHD-CORE-0.6.0
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_6.1
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-cbc hmac-md5 none
debug1: kex: client->server aes128-cbc hmac-md5 none
debug1: sending SSH2_MSG_KEXDH_INIT
debug1: expecting SSH2_MSG_KEXDH_REPLY
debug1: Server host key: DSA 6f:2c:48:80:86:ff:69:99:28:c2:21:5b:02:d4:7f:63
debug1: checking without port identifier
The authenticity of host '[mycli.abc.com]:10000 ([mycli.abc.com]:10000)' can't be established.
DSA key fingerprint is 6f:2c:48:80:86:ff:69:99:28:c2:21:5b:02:d4:7f:63.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added '[mycli.abc.com]:10000' (DSA) to the list of known hosts.
debug1: ssh_dss_verify: signature correct
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: Roaming not allowed by server
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: password,publickey
debug1: Next authentication method: publickey
debug1: Offering RSA public key: /home/todd/.ssh/id_rsa
debug1: Authentications that can continue: password,publickey
debug1: Trying private key: /home/todd/.ssh/id_dsa
debug1: Trying private key: /home/todd/.ssh/id_ecdsa
debug1: Next authentication method: password
[email protected]'s password:
debug1: Authentication succeeded (password).
Authenticated to mycli.abc.com ([mycli.abc.com]:10000).
debug1: channel 0: new [client-session]
debug1: Entering interactive session.
debug1: No xauth program.
Warning: No xauth data; using fake authentication data for X11 forwarding.
debug1: Requesting X11 forwarding with authentication spoofing.
X11 forwarding request failed on channel 0
Cli>

Pero con paramiko siempre falla:

DEBUG:paramiko.transport:starting thread (client mode): 0x22783e10L
INFO:paramiko.transport:Connected (version 2.0, client SSHD-CORE-0.6.0)
DEBUG:paramiko.transport:kex algos:['diffie-hellman-group1-sha1'] server key:['ssh-dss'] client encrypt:['aes128-cbc', '3des-cbc', 'blowfish-cbc'] server encrypt:['aes128-cbc', '3des-cbc', 'blowfish-cbc'] client mac:['hmac-md5', 'hmac-sha1', 'hmac-md5-96', 'hmac-sha1-96'] server mac:['hmac-md5', 'hmac-sha1', 'hmac-md5-96', 'hmac-sha1-96'] client compress:['none'] server compress:['none'] client lang:[''] server lang:[''] kex follows?False
DEBUG:paramiko.transport:Ciphers agreed: local=aes128-cbc, remote=aes128-cbc
DEBUG:paramiko.transport:using kex diffie-hellman-group1-sha1; server key type ssh-dss; cipher: local aes128-cbc, remote aes128-cbc; mac: local hmac-sha1, remote hmac-sha1; compression: local none, remote none
DEBUG:paramiko.transport:Switch to new keys ...
DEBUG:paramiko.transport:Adding ssh-dss host key for [mycli.abc.com]:10000: 6f2c488086ff699928c2215b02d47f63
DEBUG:paramiko.transport:Trying discovered key d7ab335994d0e5c90f8886b515faff55 in /home/todd/.ssh/id_rsa
DEBUG:paramiko.transport:userauth is OK
INFO:paramiko.transport:Authentication (publickey) failed.
INFO:paramiko.transport:Disconnect (code 2): Protocol error: expected packet SSH_MSG_USERAUTH_REQUEST, got SSH_MSG_SERVICE_REQUEST
Traceback (most recent call last):
  File "./mycli_test.py", line 13, in <module>
    oc = MyCli(hostname=hostname, username=username, password=password)
  File "/home/todd/devel/mylib/mycli.py", line 16, in __init__
    key_filename, timeout, allow_agent, look_for_keys, compress)
  File "/usr/lib/python2.7/site-packages/paramiko/client.py", line 338, in connect
    self._auth(username, password, pkey, key_filenames, allow_agent, look_for_keys)
  File "/usr/lib/python2.7/site-packages/paramiko/client.py", line 519, in _auth
    raise saved_exception
paramiko.AuthenticationException: Authentication failed.

El script de paramiko:

#!/usr/bin/env python2

import paramiko

paramiko.common.logging.basicConfig(level=paramiko.common.DEBUG)

ssh = paramiko.SSHClient()
ssh.set_missing_host_key_policy(paramiko.MissingHostKeyPolicy())
ssh.connect(hostname='mycli.abc.com', port=10000, username='admin', password='abc123')
i, o, e = ssh.exec_command('uname -a')
print o.readlines()
ssh.close()

Versión de Paramiko: 1.9.0

¿Por qué arroja el error "Error de protocolo: paquete esperado SSH_MSG_USERAUTH_REQUEST, tengo el error SSH_MSG_SERVICE_REQUEST"? ¿Cómo evitarlo?