У меня эксперементальная система, поэтому можно удалять/устанавливать все что угодно, критических данных для потери нет.
Проблема была в том что в системе были остатки от старых установок других БД, таких как MariaDB, Percona, MySQL. И хотя все предыдущие перечисленные БД были удалены с помощью apt purge, в системе всеравно кое где остались некоторые файлы/директории/скрипты от этих БД. И эти "остатки" каким то образом конфликтовали при новой установки MySQL.
Поэтому я решил эту проблему так:
sudo apt-get purge .*mariadb.* .*mysql.*
sudo apt-get autoremove
Но самое главное, ищем и удаляем остатки:
sudo locate mysql
Эта команда выдаст список оставшихся
после удаления файлов/директорий/скриптов прошлых БД. Всех их тоже надо удалить.
После этого можно устанавливать MySQL как обычно:
sudo apt install mysql-server mysql-client
Все должно пройти ОК, без всяких Errors.