Каких экспериментов?
Сначала установил mysql-5.6, потом попробовал вернуться обратно.
sudo apt-get install -f
Пробовали?
Пробовал - не получилось. Вываливался с той же ошибкой.
После нескольких часов пляски с бубном получилось.
1. Удаляем старые дистрибутивы, сохранив при этом /etc/mysql/my.cnf
sudo apt-get purge libaio1 mysql-server-5.6 mysql-server-core-5.6 libdbd-mysql-perl libdbi-perl libterm-readkey-perl
2. Удалил базы
3. Накатываем
sudo apt-get install libaio1 mysql-server-5.5 mysql-server-core-5.5 libdbd-mysql-perl libdbi-perl libterm-readkey-perl mysql-client-core-5.5
3. Сервер не запустился и ругается
can't find file './mysql/host.frm'
Делаем
sudo chown -R mysql:mysql /val/lib/mysql
После этого - все запустилось.
Еще тонкость - если при запуске ругается на пользователя debian-sys-maint и не выключается по команде service mysql stop,
то надо mysql-пользователю debian-sys-maint задать пароль из файла /etc/mysql/debian.cnf
update user set password=PASSWORD("password from /etc/mysql/debian.cnf") where User='debian-sys-maint'