My host is looking into the problem, but what confuses me is that, despite the errors, nothing shows up in my error log in the admin area - shouldn't there be some detail in here?
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).