The number of users you have isn't always the issue - unless you're on a dedicated server, don't forget that other websites and users will be using that same MySQL server.
Since this isn't a dedicated server, you won't be able to make server adjustments, your host will have to do that. Don't forget though, your site might not be causing the problems... anotehr site using that server could be using too many resources and causing trouble for MySQL.
One thing to check - edit your config file and make sure persistant connections is off.
