> max_connectionsに関しては共有サーバである為
> 予想通り変更は不可能でした。
> 
> ということは、サポート体制の充実した専用サーバを
> 借りる方がいいですね。
接続関係の設定は、max_connections以外に、key_bufferとかquey 
cash limitなどいろいろあります。
私はMySQLを使い始めて数ヶ月の初心者なのですが、たとえば
MySQL4.0.x用のmy.cnfの設定例は次のようなものがあります。

[mysqld]
max_connections = 500
key_buffer = 32M
myisam_sort_buffer_size = 64M
join_buffer_size = 1M
read_buffer_size = 1M
sort_buffer_size = 2M
table_cache = 1024
thread_cache_size = 64
wait_timeout = 1800
connect_timeout = 10
max_allowed_packet = 16M
max_connect_errors = 10
query_cache_limit = 1M
query_cache_size = 16M
query_cache_type = 1
skip-innodb

[mysqld_safe]
open_files_limit = 8192

[mysqldump]
quick
max_allowed_packet = 16M

[myisamchk]
key_buffer = 64M
sort_buffer = 64M
read_buffer = 16M
write_buffer = 16M7

ご参考になれば幸いです。