I am not sure if it will work, but try this. First you need to uninstall anything that is related to mysql:

sudo apt-get purge mysql*
sudo apt-get autoremove
sudo apt-get autoclean

Then the important bit, this error could be caused because your distribution is not upgraded recently, or at least conflicts are not resolved properly. So next thing is to upgrade it like you did before but without removing first:

sudo apt-get dist-upgrade

Now after this is done, you can try to install mysql as normal again. Hope this will work, please give a report. If it doesnt work we'll try another fix.

I get the same error. . No luck with above mentioned solutions :-(

dpkg: dependency problems prevent configuration of mysql-server:
mysql-server depends on mysql-server-5.7; however:
Package mysql-server-5.7 is not configured yet.

dpkg: error processing package mysql-server (--configure):
dependency problems - leaving unconfigured
No apport report written because the error message indicates its a followup error from a previous failure.
Processing triggers for libc-bin (2.23-0ubuntu5) ...
Processing triggers for systemd (229-4ubuntu16) ...
Processing triggers for ureadahead (0.100.0-19) ...
Errors were encountered while processing:
mysql-server-5.7
mysql-server
E: Sub-process /usr/bin/dpkg returned an error code (1)

Thank you CrypticDesigns. I went through purging, removing, and cleaning multiple times before and after dist-upgrade. It didn't work for me. Any other suggestion/ solution will be appreciated..

same problem here

I had similar problem.
Ubuntu 14.04 with preinstalled nginx + mysql 5.5. In July 2015 after one of security updates mysql doesn't finish to install. I've tried shuting down mysql-server before updating without success in updating. Today I've tried to removing and installing again mysql-server but still the same error. Then I stopped and started mysql manually in other shell during updating in aptitude, and problem disapers (ie. on aptitude I have no error message "packages partially installed: mysql-server and mysql-server-5.5")
I hope this will help someone.

Have the same problem as well and I also keep getting unable to set root password.

Ping! Same issue with my server

This worked for me :-)

Well I am having the same issue I have tried your

sudo apt-get purge mysql*
sudo apt-get autoremove
sudo apt-get autoclean

I am getting this error

Reading package lists... Done
Building dependency tree
Reading state information... Done
Note, selecting 'mysqltcl' for glob 'mysql'
Note, selecting 'mysql-mmm-agent' for glob 'mysql'
Note, selecting 'mysql-workbench' for glob 'mysql'
Note, selecting 'mysql-client-5.5' for glob 'mysql'
Note, selecting 'mysql-client-5.6' for glob 'mysql'
Note, selecting 'mysql-client-5.7' for glob 'mysql'
Note, selecting 'mysql-mmm-tools' for glob 'mysql'
Note, selecting 'mysql-common-5.6' for glob 'mysql'
Note, selecting 'mysql-server-5.0' for glob 'mysql'
Note, selecting 'mysql-server-5.1' for glob 'mysql'
Note, selecting 'mysql-server-5.5' for glob 'mysql'
Note, selecting 'mysql-server-5.6' for glob 'mysql'
Note, selecting 'mysql-server-5.7' for glob 'mysql'
Note, selecting 'mysql-utilities' for glob 'mysql'
Note, selecting 'mysql-testsuite' for glob 'mysql'
Note, selecting 'mysql-mmm-common' for glob 'mysql'
Note, selecting 'mysql-server' for glob 'mysql'
Note, selecting 'mysql-client' for glob 'mysql'
Note, selecting 'mysql-sandbox' for glob 'mysql'
Note, selecting 'mysql-client-core-5.5' for glob 'mysql'
Note, selecting 'mysql-client-core-5.6' for glob 'mysql'
Note, selecting 'mysql-client-core-5.7' for glob 'mysql'
Note, selecting 'mysql-testsuite-5.5' for glob 'mysql'
Note, selecting 'mysql-testsuite-5.6' for glob 'mysql'
Note, selecting 'mysql-testsuite-5.7' for glob 'mysql'
Note, selecting 'mysql-common' for glob 'mysql'
Note, selecting 'mysql-mmm-monitor' for glob 'mysql'
Note, selecting 'mysqltuner' for glob 'mysql'
Note, selecting 'mysql-workbench-data' for glob 'mysql'
Note, selecting 'mysql-server-core-5.1' for glob 'mysql'
Note, selecting 'mysql-server-core-5.5' for glob 'mysql'
Note, selecting 'mysql-server-core-5.6' for glob 'mysql'
Note, selecting 'mysql-server-core-5.7' for glob 'mysql'
Note, selecting 'mysql-source-5.7' for glob 'mysql'
Package 'mysql-client-5.5' is not installed, so not removed
Package 'mysql-client-5.6' is not installed, so not removed
Package 'mysql-server-core-5.6' is not installed, so not removed
Package 'mysql-client-core-5.5' is not installed, so not removed
Package 'mysql-client-core-5.6' is not installed, so not removed
Note, selecting 'mysql-common' instead of 'mysql-common-5.6'
Package 'mysql-server-5.5' is not installed, so not removed
Package 'mysql-server-5.6' is not installed, so not removed
Package 'mysql-server-core-5.5' is not installed, so not removed
Package 'mysql-testsuite-5.5' is not installed, so not removed
Package 'mysql-testsuite-5.6' is not installed, so not removed
Package 'mysql-server-5.0' is not installed, so not removed
Package 'mysql-server-5.1' is not installed, so not removed
Package 'mysql-server-core-5.1' is not installed, so not removed
Package 'mysql-mmm-agent' is not installed, so not removed
Package 'mysql-mmm-common' is not installed, so not removed
Package 'mysql-mmm-monitor' is not installed, so not removed
Package 'mysql-mmm-tools' is not installed, so not removed
Package 'mysql-sandbox' is not installed, so not removed
Package 'mysql-utilities' is not installed, so not removed
Package 'mysql-workbench' is not installed, so not removed
Package 'mysql-workbench-data' is not installed, so not removed
Package 'mysqltcl' is not installed, so not removed
Package 'mysqltuner' is not installed, so not removed
Package 'mysql-source-5.7' is not installed, so not removed
Package 'mysql-testsuite' is not installed, so not removed
Package 'mysql-testsuite-5.7' is not installed, so not removed
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
dbconfig-mysql : Depends: mysql-client but it is not going to be installed or
mariadb-client but it is not going to be installed or
virtual-mysql-client
E: Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.

Still having the same problem even after following @ForYourIT 's answer. This is driving me insane.