Comment 8 for bug 230174

Hi there.
Since I had the same problem and didn't find a complete Solution on the Net.
So, I wanted to share my solution with other people having this problem.

The Problem is:
I am running a dapper version of Ubuntu. Since some piece of software (e.g. Nagios2) requires a newer version, someone added this to the source.list (e.g. hardy).
Within the Installation of the software, it seems that libssl also updated to a newer version.
Since the modified entries from the sources.list were removed imidiatly or the updates-repository for this version weren't added, the update isn't executed for the newer Version of libssl.

Solution is:
Install newest openssh-server / openssh-client
If the keygeneration does not work, see which libssl-version is installed (gutsy, feisty, hardy etc.) and add the corresponding update-repository to the source.list.
Running apt-get update; apt-get install libssl0.9.8 should then update to the latest update-version.
Now, keygeneration should be fine.

I put exactly this way (except SSH Installation) into a bash script.
Running it solved, the Problem on all of my machines.
Please make sure - if running it - that all it only updates libssl0.9.8. If it tells you that it has to remove some stuff you should overthink it again.
On all of my machines, it only updated libssl0.9.8 and worked fine.

Have fun