We also had this issue frequently on our old server. We had to restart mySQL through SSH but it's never recommended to restart mySQL unless you have no choice as it can cause a table to be corrupt upon mySQL restarting.
@Wesker, this is controlled by the MySQL 'max_connections' setting. If you are running your own server, you can raise this value if the current value is troublesome. However, OP is using a shared/managed host, so that isn't relevant.
Additionally, it is possible to shutdown/restart MySQL gracefully. I've only ever seen corruption from killing it unexpectedly (ie via killall or OOM).