They always tell you things like that, it's most often an excuse, and it's the reality of shared hosting I'm afraid.
In general servers get filled up with sites quickly, as performance declines, the hosting company will add new servers to the pool and also manage the contention ratio (i.e. the ratio of heavy users to light users) to spread the load - but there will always be one or more heavy users on a shared host - that's why it's cheap.
Some manage this better than others but it really is a case of "you get what you pay for".
If, for example, you're in the UK and your server is in eastern europe then you might find the roundtrip time is long and finding hosting closer to home, or closer to the majority of your users might be more effective than worrying about something outside of your control.
You could also try caching pages, examining your site with google page speed or yslow to see if you can make your site more efficient - replacing locally hosted jquery scripts with CDN copies would have a positive effect for example.