We are currently running Fedora Core 6 (with Plesk 8.2). The php version we are currently running (PHP Version 5.1.6) has been compiled without mcrypt (phpinfo attached).
We are not actually sure whether mcrypt is actually installed on the server:
1) Install mcrypt if it is not installed already
2) Recompile PHP (if needed?)