Intermittent "Can't Connect To MySQL Server"

Recently, I started getting small periods of intermittent connection errors about once every hour, lasting for about 1 to 5 minutes each time:
Can't connect to local MySQL server through socket
'/var/lib/mysql/mysql.sock'

I enabled the error log and did some other monitoring and established 2 things:
- the server doesn't crash/restart, it keeps running throughout the errors
- the errors do not match the load on the website, as sometimes when 500 users are online there are no errors, but when 300 are online they may by prolific

I checked many forums and then made 4 changes:
- changed the directory containing the mysql.sock file so only file owners or superusers can delete files from it
- I changed the default socket file setting in both my.cnf and php.ini
- I read about SELinux causing such a problem, so I disabled SELinux completely, rebooted the server and double-checked that it is indeed disabled.

Despite all these changes, I still get the errors. I then read that there is a workaround by using TCP/IP instead of the sock file. I tried that, but I still get the error intermittently in the form of:
Can't connect to MySQL server on 127.0.0.1

MySQL server 4.1.20, PHP 4.3.9, client API 4.1.20, CentOS 4.3, Intel P4 2.8GHz 1GB RAM