Solution:
In case anyone else faces this, it’s a case of PHP not having access to the mysql client libraries. Having a MySQL server on the system is not the correct fix. Fix for ubuntu (and PHP 5):
sudo apt-get install php5-mysql
After installing the client, the webserver should be restarted. In case you’re using apache, the following should work:
sudo service apache2 restart