А может mysql криво стоит, не бывает проблем из ничего. Что-нибудь непонятное с настройками делалось? Гадать что не так не буду, это долго и не умею гадать

Можно сделать uninstall, стереть все следы прибывания и установить все заново. Но на VDS проще всего сделать полный бэкап, слить его себе и переставить VDS полностью, если после переустановки mysql не поднимится, то добивать супорт.

Хостер кто?