dpkg: invoke-rc.d: initscript mysql, action "start" failed

Solution from Titanicx worked for me. Ran

dpkg -S etc/mysql

to see that mysql-common was the problem. Removed MySQL completely:

sudo apt-get remove --purge mysql-server mysql-client mysql-common
sudo apt-get autoremove
sudo apt-get autoclean

I had this problem before. MySQL Daemon will be started just right after configuring the package, and if there is any errors in MySQL configuration or problems with accessing data directory, then the job will fail.

Checking MySQL error log on /var/log/mysql/error.log can help you in this case.

In my case, there was an access error caused by apparmor:

150131 19:38:23  InnoDB: Operating system error number 13 in a file operation.
InnoDB: The error means mysqld does not have the access rights to
InnoDB: the directory.
InnoDB: File name ./ibdata1
InnoDB: File operation call: 'open'.
InnoDB: Cannot continue operation.

And it just solved by editing appropriate apparmor file.

My issue was that I had /tmp sym-linked elsewhere and Apparmor didn't like it.

Editing /etc/apparmor.d/abstractions/user-tmp and adding the real path to /tmp fixed it and allowed MySQL to start successfully.

(Source of inspiration)