It seems that when I have more than one key held by the agent, any authentication that would require anything but the first key would fail. The trace is copied down below. I also added some dedug info at the packet level. Could it be that there should not be a [service-request] following the [userauth-failure] with the wrong key, but directly a new [userauth-request]?
Thanks,
-Gellule

DEBUG:paramiko.transport:starting thread (client mode): 0x2514550L
INFO:paramiko.transport:Connected (version 2.0, client 3.2.9.1)
Write packet [kexinit], length 406
Read packet [ignore], length 5
Read packet [kexinit], length 461
DEBUG:paramiko.transport:kex algos:['diffie-hellman-group1-sha1'] server key:['ssh-dss'] client encrypt:['aes128-cbc', '3des-cbc', 'twofish128-cbc', 'cast128-cbc', 'twofish-cbc', 'blowfish-cbc', 'aes192-cbc', 'aes256-cbc', 'twofish192-cbc', 'twofish256-cbc', 'arcfour'] server encrypt:['aes128-cbc', '3des-cbc', 'twofish128-cbc', 'cast128-cbc', 'twofish-cbc', 'blowfish-cbc', 'aes192-cbc', 'aes256-cbc', 'twofish192-cbc', 'twofish256-cbc', 'arcfour'] client mac:['hmac-sha1', 'hmac-sha1-96', 'hmac-md5', 'hmac-md5-96'] server mac:['hmac-sha1', 'hmac-sha1-96', 'hmac-md5', 'hmac-md5-96'] client compress:['none', 'zlib'] server compress:['none', 'zlib'] 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
Write packet [kex30], length 133
Read packet [ignore], length 5
Read packet [kex31], length 630
Write packet [newkeys], length 1
Read packet [ignore], length 5
Read packet [newkeys], length 1
DEBUG:paramiko.transport:Switch to new keys ...
DEBUG:paramiko.transport:Trying SSH agent key fbd3bc799a422891ffc58f9212539a13
Write packet [service-request], length 17
Read packet [ignore], length 5
Read packet [service-accept], length 17
DEBUG:paramiko.transport:userauth is OK
Write packet [userauth-request], length 550
Read packet [ignore], length 1005
Read packet [userauth-failure], length 24
INFO:paramiko.transport:Authentication (publickey) failed.
DEBUG:paramiko.transport:Trying SSH agent key 939d6a49f527e8f0c53e9ec509ff913a
Write packet [service-request], length 17
Read packet [ignore], length 5
Read packet [disconnect], length 54
INFO:paramiko.transport:Disconnect (code 2): Protocol error: packet 5 in interactive
paramiko.AuthenticationException: Authentication failed.