On Ubuntu 7.04 (Feisty Fawn), mysql_connect and all those leftover functions from php3/php4 do not work. YOu have to go into /etc/php5/apache2/php.ini and add the .so file. Do this:

sudo vi /etc/php5/apache2/php.ini

Add:

extensions = mysql.so

Make sure to restart apache:

sudo /etc/init.d/apache2 restart