The fact that you are using Graphene has no bearing on which caching plugin is the best for you. I would also recommend using W3 Total Cache, but it also requires some careful setting up to get the best out of it.
It seems to me that your hosting company is taking the easy way out – instead of trying to find the cause of the problem, they simply jump plugin. What is the error message being displayed?