I have a solution. It's called XenForo. It's only in Beta, but I've found it's more stable than vB4.
I know that this is kind of a smart ass answer, but I can't tell you how many times I got the "too many connections" error with vB. I kept thinking that it was something to do with my hosting and I kept upgrading. Now that I'm on XF I have yet to have it with the same traffic. The difference is amazing.
Good for your host helping out, but man I hated it when stuff like that happened. You just feel so damned helpless.