There could be a few different reasons for this to happen.
Have you indexed your tables correctly? This will have a huge impact on the speed.
Do you use "ORDER BY RAND"? If you do, rethink the queries. Those queries take way to long to do.
Can you post the queries that give you problems?
To answer your questions: MySQL can handle lots of connections at the same time, it is all about the computer it is run on. If it is not fast enough, or not set up properly, you will get into troubles. With a shared server it is up to the database access for everyone else as well, even if you do everything right you will have a slow database access if someone else have slow queries. So I would say that the time to upgrade to a dedicated server is before the site is released. An additional advantage is that the security is much better on a dedicated server where only you have access to the database.
