Comment 15 for bug 590639

It hasn't been fixed yet, unfortunately :-(

So here is a small howto for (k)ubuntu if you need to fix it (root privileges assumed):

1) create a directory somewhere, e.g. /usr/src/openssl, chdir there and run:
apt-get source openssl
apt-get build-dep openssl

2) edit ./openssl-0.9.8k/debian/patches/aesni.patch: on line 1956 change
+ ENGINE_add (toadd);
to
+ if (ENGINE_add (toadd))

3) edit /openssl-0.9.8k/crypto/engine/eng_all.c: on line 64 add this new line (as first row in the ENGINE_load_builtin_engines(void) function):
OPENSSL_cpuid_setup();

4) now build the packages (from /usr/src/openssl/openssl-0.9.8k)
dpkg-buildpackage

5) Then you'll get new packages in /usr/src/openssl. Install libssl0.9.8_0.9.8k-7ubuntu8_*.deb and reboot (to test apache you do not need reboot, just restart apache). Be carefull on updates not to install the original version from the repositories.