Не удается войти в свежий установленный Ubuntu Server 16.04.3: неверный вход?

Кажется, у вас есть артефакты из библиотеки mysql-client, используемые другим приложением. Я предлагаю сделать

sudo aptitude search libmysql | grep '^i'

Это покажет установленные версии libmysql, которые вы могли бы попытаться удалить один за другим с помощью apt. Возможно, что одно из ваших установленных приложений может зависеть от указанной версии и принудительно удалить себя в процессе.