Tente remover /etc/php5/mods-available/mcrypt.ini e /etc/php5/cli/conf.d/20-mcrypt.ini caso ainda exista algum deles e tente instalá-lo novamente com o apt- obter
sudo rm -f /etc/php5/mods-available/mcrypt.ini
sudo rm -f /etc/php5/cli/conf.d/20-mcrypt.ini
O problema deve estar vindo do primeiro arquivo, mas exclua o segundo também, só para ter certeza.