FIRST: I think this should be the primary bug (not duplicate of #1574168 or #1574204 ) and because it has the most useful information in it. Someone should fix this.

----------------------------------

SECOND: 

Searching the web I found, that in the XENIAL RELEASE NOTES the problem is already addressed and links to bug #1571865 :

* https://wiki.ubuntu.com/XenialXerus/ReleaseNotes#MySQL_5.7

So this bug should also be marked as DUPLICATE of bug #1571865 !

----------------------------------

THIRD:

So this bug should be considered of HIGH IMPORTANCE.

----------------------------------

For me, I could get this going on one of my computers moving /etc/mysql/my.cnf out of the way and running "apt-get -f install".

On another system this did NOT work. I did an Update from Ubuntu 14.04 to 16.04. I simply cannot get mysql-server.5.7 package getting installed and the server to be run.

I tried the solutions mentioned in bug #1571865 and the article in askubuntu: http://askubuntu.com/questions/760724/16-04-upgrade-broke-mysql-server. Nothing of the worked to get - even purging everything out of the way.

#> dpkg --configure -a
# Setting up mysql-server-5.7 (5.7.12-0ubuntu1) ...
# initctl: Unable to connect to Upstart: Failed to connect to socket /com/ubuntu/upstart: Connection refused
# Job for mysql.service failed because the control process exited with error code. See "systemctl status mysql.service" and "journalctl -xe" for details.
# invoke-rc.d: initscript mysql, action "start" failed.
# dpkg: error processing package mysql-server-5.7 (--configure):
# subprocess installed post-installation script returned error exit status 1
# 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
# Errors were encountered while processing:
# mysql-server-5.7
#  mysql-server

# > journalctl -xe
# Apr 26 15:52:37 teneriffa mysqld[31909]: 2016-04-26T13:52:37.020799Z 0 [Note] InnoDB: Shutdown completed; log sequence number 166631303
# Apr 26 15:52:37 teneriffa mysqld[31909]: 2016-04-26T13:52:37.024809Z 0 [Note] InnoDB: Removed temporary tablespace data file: "ibtmp1"
# Apr 26 15:52:37 teneriffa mysqld[31909]: 2016-04-26T13:52:37.024898Z 0 [Note] Shutting down plugin 'MEMORY'
# Apr 26 15:52:37 teneriffa mysqld[31909]: 2016-04-26T13:52:37.024910Z 0 [Note] Shutting down plugin 'PERFORMANCE_SCHEMA'
# Apr 26 15:52:37 teneriffa mysqld[31909]: 2016-04-26T13:52:37.025086Z 0 [Note] Shutting down plugin 'MRG_MYISAM'
# Apr 26 15:52:37 teneriffa mysqld[31909]: 2016-04-26T13:52:37.025093Z 0 [Note] Shutting down plugin 'MyISAM'
# Apr 26 15:52:37 teneriffa mysqld[31909]: 2016-04-26T13:52:37.025104Z 0 [Note] Shutting down plugin 'CSV'
# Apr 26 15:52:37 teneriffa mysqld[31909]: 2016-04-26T13:52:37.025113Z 0 [Note] Shutting down plugin 'sha256_password'
# Apr 26 15:52:37 teneriffa mysqld[31909]: 2016-04-26T13:52:37.025119Z 0 [Note] Shutting down plugin 'mysql_native_password'
# Apr 26 15:52:37 teneriffa mysqld[31909]: 2016-04-26T13:52:37.025353Z 0 [Note] Shutting down plugin 'binlog'
# Apr 26 15:52:37 teneriffa mysqld[31909]: 2016-04-26T13:52:37.027216Z 0 [Note] /usr/sbin/mysqld: Shutdown complete
# Apr 26 15:52:37 teneriffa systemd[1]: mysql.service: Main process exited, code=exited, status=1/FAILURE

# > systemctl status mysql.service
● mysql.service - MySQL Community Server
   Loaded: loaded (/lib/systemd/system/mysql.service; enabled; vendor preset: enabled)
   Active: activating (start-post) (Result: exit-code) since Di 2016-04-26 15:54:06 CEST; 16s ago
  Process: 615 ExecStart=/usr/sbin/mysqld (code=exited, status=1/FAILURE)
  Process: 611 ExecStartPre=/usr/share/mysql/mysql-systemd-start pre (code=exited, status=0/SUCCESS)
 Main PID: 615 (code=exited, status=1/FAILURE);         : 617 (mysql-systemd-s)
    Tasks: 2 (limit: 512)
   CGroup: /system.slice/mysql.service
           └─control
             ├─617 /bin/bash /usr/share/mysql/mysql-systemd-start post
             └─853 sleep 1

... followed by the same messges as on journalctl -xe