The php mcrypt module, required by Magento, wasn’t present on our Plesk VPS. Here’s how to add it from SSH:

(1) Add the repository. For example, to add EPEL:
rpm -Uvh http://dl.fedoraproject.org/pub/epel/6/x86_64/epel-release-6-8.noarch.rpm

(2) Install the php-mcrypt module:
yum install php-mcrypt