К словам хостера, конечно, нужно относиться критически, т. е. не стоит верить на слово, а нужно во всем разбираться. Версию хостера нужно проверять. Да и сервер базы данных в VPS - это составная часть самого VPS.
проблема может быть как в самом магазине, так и в настройках базы данных или VPS. Просто вы должны понимать, что работа по настройке того же VPS или выделенного сервера не стоит дешевле 800 руб/час ($25/час) даже у украинских специалистов. А тем более, что вы желаете срочно и в выходной день. На поиск причины может потребоваться несколько часов. freelancer совершенно верное подсказывает вам решение для анализа запросов.
Я бы тоже воспользовался им для конкретизации картины.
Если у вас имеется некоторый опыт, то воспользуйтесь советом freelancer-а.
Если вы совершенно не знаете как настраивать VPS, то милости просим, обращайтесь в личку.