AVISO: esta pergunta e resposta são anteriores ao bug do OpenSSL, Heartbleed.
Primeiro, você precisa remover completamente a instalação antiga: (Isso vai quebrar a maioria dos sistemas! Tenha cuidado! A maioria das pessoas vai se arrepender disso) limpeza do apt-get openssl
Você pode querer limpar a casa executando:
apt-get autoremove && apt-get autoclean
Em seguida, você deve baixar e compilar a versão desejada ( lista completa )
wget https://www.openssl.org/source/openssl-1.0.1g.tar.gz