I have exactly the same problem but with ubuntu 10.04(which is debian based).
Here is my log:
carlos@carlos:~$ ssh
[email protected]
[email protected]'s password:
Linux ns353440.ovh.net 2.6.38.2-xxxx-std-ipv6-64 #1 SMP Tue Apr 12 17:19:35 UTC 2011 x86_64 GNU/Linux
Ubuntu 10.04.3 LTS...