When 5-10 user login the same time, server not responding anymore for 20 minutes; site maintenance mode

We are running our intranet on a webhosting provider. At first, the provider did not have our requirements at all (some Drupal requirements not possible on a shared hosting because it might affect other customers on that hosting). So paid him more to move from a shared hosting to an own server.

However, when we now had our first intranet training, and 5-10 users tried to login the same time, suddenly the server seemed to be down. I am not sure if the server was really down, but it was not possible to get any server response. Always timeout. After a while, at least a Drupal "Site in maintenance mode" message came up. I could get the FTP server responding as well as open phpMyAdmin.

Our hosting provider tells us it is not an issue with the server but with our system/software, i.e. Drupal, but I cannot believe that because we are running a standard Drupal 6 installation with CCK, Views, etc. They monitored the system while we were trying to login with many users. According to them, the swap file (2 GB) gets used up to 70% while it should only be 10% or so normally. So they argue it is our software which is not correct:

http://img338.imageshack.us/img338/6410/100525swap1.jpg
http://img697.imageshack.us/img697/7562/100525swap2.jpg
http://img189.imageshack.us/img189/1083/100525swap3.jpg
http://img248.imageshack.us/img248/3631/100525swap4.jpg

Additional information:
- The maintenance screen showed "The MySQL error was: Too many connections." as the reason (as far as I remember; is there any log file to look into?)
- In phpMyAdmin I can see a lot of tables are marked having "Overhead" in particular "cache_form" (24.8 MiB) and "watchdog" (22.7 MiB); in total: size is 63.8 MiB plus overhead is 49.1 MiB
- Doing a "Check Table" on all table before returned "1 client is using or hasn't closed the table prope..." or more for many tables (now, however, it seems to be gone)

Can someone help why this could happen?