Make sure your host is running the latest version of MySQL 4.1x . I believe there were issues w.r.t. max_connections in some of the ealier releases.
I encountered the problem when upgrading to phpMyAdmin version 2.7.0-pl1 on my test server. As soon as I examined a WordPress DB using this version of phpMyAdmin, for some reason threads associated with the WP database connection users started to be spawned by the bucketful. Even though there is supposed to be always one connection reserved for the root user, I couldn't log on at the MySQL console with a "max_connections for user" error. A reboot of the server did not clear the connections - and none of my applications could connect to MySQL.
I amended the max_connections value in the INNODB section from 0 to 800 (see below) and restarted MySQL - et voila! Everything back to normal
I've finally got my reason to upgrade to 5 I think , lol.
Relevant section from Mysql my.ini file:
# Number of threads allowed inside the InnoDB kernel. The optimal value
# depends highly on the application, hardware as well as the OS
# scheduler properties. A too high value may lead to thread thrashing.
#The maximum number of active connections for a single user (0 = no limit).
#note from Sokrates: changed above value to 800