Caso alguém mais enfrente isso, é um caso do PHP não ter acesso às bibliotecas do cliente mysql. Ter um servidor MySQL no sistema não é a correção correta. Correção para Ubuntu (e PHP 5):
sudo apt-get install php5-mysql
Depois de instalar o cliente, o servidor web deve ser reiniciado. Caso você esteja usando o apache, o seguinte deve funcionar:
sudo service apache2 restart
