A correção que funcionou para mim foi relativamente simples:
A solução: adicione a seguinte linha ao arquivo /etc/php5/apache2/php.ini
:
extension=mcrypt.so
Esta linha faz com que a extensão mcrypt seja carregada automaticamente quando o servidor é reiniciado. Eu não sei porque as instruções do Arda não conseguiram o mesmo no meu caso, mas acho que pode ter algo a ver com a atualização de versões anteriores do Linux.