sudo apt-cache search mcrypt |grep php

vedi quali sono i pacchetti installabili... probabilmente è solo qualcosa che non va nel nome del pacchetto (nel mio caso sarebbe php5.6-mcrypt)