The MySQL server is not configured to handle as many simultaneous users as it's getting. As Noobarmy says, the host will have to fix it, because they control this.
Ideally, when dealing with MySQL-based websites, the web server will be configured to not allow more connections than the MySQL server can handle at a time. Our busiest web servers allow up to 256 simultaneous page views, and the MySQL servers than feed them data handle at least 500 connections. In this way, when you get a connect for a page view, the web server is assured that it will be able to connect to all the resources it needs to fulfill that request, otherwise, it delays accepting the request. Browsers can handle connect delays... most scripts can't.
Thank you very much for the explaination. I do appreciate you going into detail on it.