After a long battle with technology, Steven A. DuChene wrote:
  

But if that was the problem then the command line invocation on the Apache
server should not work. I.E. if it was a port or firewall issue.
    

apache:~$ mysql -u user --password=BLAH --host Mysql
apache:~$ php -r '$c=mysql_connect("Mysql","user","BLAH"); if(!$c){ 
die("barf:".mysql_error()); }'

...both should work.

  

Can't connect to MySQL server on 'Mysql' (13)
in /home/minime/public_html/testmysqlconnect_script.php on line 6
        

Are you running in safe mode?  Is Mysql's mysqld listening on port 3306? 
Is there any firewall in the way on that port?
      

No firewall.  Are you running php-web in safe mode?  Take a really good look 
at the settings for mysql in your php.ini, and make sure they're all right.

  

Apache system is running Fedora9 while the Mysql system is a OpenSuSE-10.1
    

SuSE is buggy, but the problem as you've described it is not a SuSE bug.  The 
shotgun debugging approach would be to start up "tcpdump -s0 -w dump.pcap 
port 3306" on apache, then run both the mysql command-line client connect 
attempt and the bad PHP script on apache.  Then stop the tcpdump, then look 
at dump.pcap with wireshark, then play "one of these things is not like the 
other".