Install scripts fail on Ubuntu 8.04 with "PHP module mysql is required" error

When I try and install any scripts that require the PHP module I get the following error from Virtualmin:

PHP module mysql is required ..

Module is not available even after installation!

I have the php5-mysql module installed, it's enabled in php.ini and the output from phpinfo() on a test page on the same virtual server shows the mysql module working, and that the server is reading the correct php.ini file.

I've tried purging and removing php5-mysql and I've restarted apache and webmin multiple times, still doesn't work.