The SSH server on this host is using a weak (blacklisted) key. A weakness has been discovered in the random number generator used by OpenSSL on Debian and Ubuntu systems. As a result of this weakness, certain encryption keys are much more common than they should be, such that an attacker could guess the key through a brute-force attack given minimal knowledge of the system. This particularly affects the use of encryption keys in OpenSSH, OpenVPN and SSL certificates. This vulnerability only affects operating systems which (like Ubuntu) are based on Debian. However, other systems can be indirectly affected if weak keys are imported into them. All SSL and SSH keys generated on Debian-based systems (Ubuntu, Kubuntu, etc) between September 2006 and May 13th, 2008 may be affected.
Upgrade your openssl package and subsequently regenerate any cryptographic material. Check references for detailed information on fixing this vulnerability.