After installing Ubuntu 13.10 with PHP 5.5.3 I kept getting the "Laravel Requires the mcrypt PHP extension" when trying to run artisan commands. Running the following commands on my server fixed the problem.

gistfile1.sh

# Make sure you have php5-mcrypt installed first.  If not, run
sudo apt-get install php5-mcrypt

# Add a symlink for mcrypt.ini in the PHP5 apache config directory
sudo ln -s /etc/php5/conf.d/mcrypt.ini /etc/php5/apache2/conf.d/20-mcrypt.ini

# Restart apache
sudo service apache2 restart