First would be to figure out what is going on, once you do that it should be pretty easy. (or at least, you'll know whether it's possible on that host)
Do you have access to the server via ssh ? try that. (ssh is really good - I wouldn't even consider a hosting company that didn't provide full access via ssh)
Is there indeed a command: /usr/bin/mysql ? (maybe it's in /usr/local some place?)
Try it via perl (or even a shell) OFTEN php is compiled with limitations.
Try using passthru on other commands and see if they work.
Do a little investigating to see if httpd is chroote'd. (this is sometimes the case, but rare)
Try and see if that tells you anything.
Could be ulimit or php settings or (doubtful) the system is overworked.
My guess is either the command /usr/bin/mysql isn't actually present (from the web servers perspective) or php has been compiled with severe restrictions.
I've seen some ISP's limit the number of processes you can have at any given time, down to laughably small numbers. (which is unfortunate, one way to reduce memory requirements on long running processes is via the use of fork for memory intensive parts) if mysql is actually a shell wrapper, the process limitations can become a factor. (doubtful)
I deal in different hosts all the time, often ISP's (especially the cheap-o packages that are supposed to be "easy to use") totally mess up php. Avoid them at all costs, you'll spend more time and $$ screwing around with the limitations than you'd save by going with a better host.