Comment 3 for bug 1369710

Jeremy, seems to be this is an Ubuntu trusty packaging issue. I made some tests in a clean vagrant/trusty box:

$ sudo apt-get install -y php5-mcrypt php5-cli
$ dpkg -l | grep php5
ii php5-cli 5.5.9+dfsg-1ubuntu4.4 amd64 command-line interpreter for the php5 scripting language
ii php5-common 5.5.9+dfsg-1ubuntu4.4 amd64 Common files for packages built from the php5 source
ii php5-json 1.3.2-2build1 amd64 JSON module for php5
ii php5-mcrypt 5.4.6-0ubuntu5 amd64 MCrypt module for php5
ii php5-readline 5.5.9+dfsg-1ubuntu4.4 amd64 Readline module for php5

This small test program from php doc site also fail:
vagrant@vagrant-ubuntu-trusty-64:~$ cat test.php
<?php
    $algorithms = mcrypt_list_algorithms("/usr/local/lib/libmcrypt");

    foreach ($algorithms as $cipher) {
        echo "$cipher<br />\n";
    }
?>
vagrant@vagrant-ubuntu-trusty-64:~$ php test.php
PHP Fatal error: Call to undefined function mcrypt_list_algorithms() in /home/vagrant/test.php on line 2
vagrant@vagrant-ubuntu-trusty-64:~$

Related upstream ubuntu bugs:
Incorrect installation directory in Trusty
https://bugs.launchpad.net/ubuntu/+source/php5-mcrypt/+bug/1261655

put ini in correct path
https://bugs.launchpad.net/ubuntu/+source/php-mcrypt/+bug/1243568

So after manual creation of the missing symlink the test php runs well.
$ ln -s /etc/php5/mods-available/mcrypt.ini /etc/php5/cli/conf.d/

The package version number seems strange also php5-mcrypt 5.4.6 vs. php5-cli 5.5.9.