Я был в той же ситуации, и я нашел более простое решение (для 12.04 LTS):
sudo apt-get install openssl = 1.0.1-4ubuntu5.12 libssl1.0.0 = 1.0 .1-4ubuntu5.12 libssl-dev = 1.0.1-4ubuntu5.12
Это запрашивает у меня DOWNGRADE этот пакет, и, отвечая да, пакеты обновляются.
It кажется, что пакеты openssl из более нового дистрибутива ubuntu (кванта или чего-то) прокрались в мою установку, когда я попытался получить какой-то пакет из дистрибутива. Поскольку репозитории безопасности в sources.list указываются на точные, пакеты из более новых дистрибутивов не могут быть обновлены apt-get dist-upgrade.