I had that problem at first on my Yellowdog linux box. The commandline version of the PHP it installed, didnt have --with-mysql set. You are most likely going to have to recompile PHP for commandline use and inclue the mysql libraries/headers.
To do this, find out the entire configure string for your web based PHP (use the phpinfo() function in a web page to find it at the top). Copy that, then edit out "--with-apxs" (if that is how it was configured, usually the case though, as the alternative would be something else) and ADD "--without-apache --enable-force-cgi-redirect".
Then recompile and install. It should NOT alter your php.in... should NOT alter you php for your webserver either... BUT, just to be on the safe side, I would suggest you make copies of those two files before you do this, just in case.
This is normally where those things are installed by default with redhat flavour os distributions (you may find yours in different places):
cp /etc/php.ini /etc/php.ini~
cp /usr/lib/apache/libphp4.so /usr/lib/apache/libphp4.so~
Anyhow, this is how I got my command line php installed to act exactly like my web version, so i had no guesswork to do with crontab php scripts (and shell php scripts). Hope this helps... if you are using mandrake, or some other OS... your milage may vary.