Comment 5 for bug 237894

I had the same issue. I built OpenSSH from source and still had the problem. I installed the latest updates and the problem is gone. I don't know which of the updates fixed it - none of them seemed obviously related to ssh. Here are the versions of OpenSSH & the updates that "fixed" the issue:

$ ssh -v
OpenSSH_5.0p1, OpenSSL 0.9.8g 19 Oct 2007

Commit Log for Mon Jun 9 08:25:35 2008

Upgraded the following packages:
apache2 (2.2.8-1ubuntu0.1) to 2.2.8-1ubuntu0.2
apache2-mpm-prefork (2.2.8-1ubuntu0.1) to 2.2.8-1ubuntu0.2
apache2-utils (2.2.8-1ubuntu0.1) to 2.2.8-1ubuntu0.2
apache2.2-common (2.2.8-1ubuntu0.1) to 2.2.8-1ubuntu0.2
gnome-about (1:2.22.2-0ubuntu2) to 1:2.22.2-0ubuntu3
gnome-desktop-data (1:2.22.2-0ubuntu2) to 1:2.22.2-0ubuntu3
initramfs-tools (0.85eubuntu36) to 0.85eubuntu39.1
libgksu2-0 (2.0.5-1ubuntu5) to 2.0.5-1ubuntu5.1
libgnome-desktop-2 (1:2.22.2-0ubuntu2) to 1:2.22.2-0ubuntu3
libsmbclient (3.0.28a-1ubuntu4) to 3.0.28a-1ubuntu4.1
python-launchpad-bugs (0.2.30) to 0.2.30.1
samba-common (3.0.28a-1ubuntu4) to 3.0.28a-1ubuntu4.1
smbclient (3.0.28a-1ubuntu4) to 3.0.28a-1ubuntu4.1
tzdata (2008b-1ubuntu1) to 2008c-1ubuntu0.8.04
tzdata-java (2008b-1ubuntu1) to 2008c-1ubuntu0.8.04
ufw (0.16.2) to 0.16.2.1
virtualbox-ose-modules-generic (24.0.1) to 24.0.3
xserver-xorg-video-cirrus (1:1.1.0-8) to 1:1.1.0-8ubuntu1

Installed the following packages:
virtualbox-ose-modules-2.6.24-18-generic (24.0.3)