Same root password setting problem here, mine possibly caused by an unsuccessful manual installation of mysql server 5.6 previously. A thorough mysql uninstallation is no easy task. I purged/reinstalled for hours then finally solved it with

sudo dpkg --purge mysql-client-core-5.5 # or alternative version
sudo dpkg --purge mysql-client
sudo dpkg --purge mysql-server-core-5.5 # or alternative version
sudo dpkg --purge mysql-common
Basically I just type

sudo dpkg --purge mysql # followed by two tabs
Then --purge any packages the terminal auto-completes. Purge mysql-common at last because of some dependency problems.

Use above dpkg commands in addition to

sudo apt-get --purge remove mysql-server
sudo apt-get --purge remove mysql-client
sudo apt-get --purge remove mysql-common
sudo apt-get autoremove
sudo apt-get autoclean
Also I tried Greq's method

sudo rm -rf /etc/mysql
At this point, to make sure mysql is fully removed, check with

which mysql
mysql --version
The first one should return no output instead of a folder. The second should return mysql is not installed instead of a version number. Otherwise the removal is still incomplete.

The significance of dpkg --purge is, when using apt-get alone, which mysql and mysql --version behave like mysql is still there.

Before reinstallation, reconfigure dpkg and update

sudo dpkg --configure -a
sudo apt-get update
Problem resolved finally. Hope it will be helpful for other people.
Hatte mal was ähnliches und das hat geholfen