Can't start the MySQL service on a recently upgraded VM

I have a VM running Ubuntu server which I just upgraded to 14.04. The VM provides access to a MySQL database. However, after upgrading, the database refuses to start and I don't know enough about it to figure it out:

root@vm-1 ~ $ service mysql start
start: Job failed to start

I checked /var/log/mysql/error.log and found:

141001 20:23:10 [Note] Server hostname (bind-address): '127.0.0.1'; port: 3306
141001 20:23:10 [Note]   - '127.0.0.1' resolves to '127.0.0.1';
141001 20:23:10 [Note] Server socket created on IP: '127.0.0.1'.
141001 20:23:10 [ERROR] Can't start server : Bind on unix socket: Permission denied
141001 20:23:10 [ERROR] Do you already have another mysqld server running on socket: /var/run/mysqld/mysqld.sock ?
141001 20:23:10 [ERROR] Aborting

141001 20:23:10  InnoDB: Starting shutdown...
141001 20:23:11  InnoDB: Shutdown completed; log sequence number 24590151085
141001 20:23:11 [Note] /usr/sbin/mysqld: Shutdown complete

You can find the entire contents of the file here. Note that I deleted it just before running the service command shown above so everything there is from a single attempt to start the MySQL service.

I also checked the obvious:

$ ps ax | grep mysql
 3623 pts/1    S+     0:00 grep --color mysql
$ rm /var/run/mysqld/mysqld.sock
rm: cannot remove ‘/var/run/mysqld/mysqld.sock’: No such file or directory
$ netstat | grep 3306

I made sure the database directory has the right permissions:

$ chown -R mysql:root /data/database/

I tried running strace but could see nothing obvious. I understand very little of it though, so you can find the output here.

Finally, my /etc/mysql/my.cnf is:

[client]
port        = 3306
socket      = /var/run/mysqld/mysqld.sock
[mysqld_safe]
socket      = /var/run/mysqld/mysqld.sock
nice        = 0
[mysqld]
user        = mysql
socket      = /var/run/mysqld/mysqld.sock
port        = 3306
basedir     = /usr
datadir     = /data/database
tmpdir      = /tmp
skip-external-locking
bind-address        = 127.0.0.1
key_buffer      = 16M
max_allowed_packet  = 16M
thread_stack        = 192K
thread_cache_size       = 8
myisam-recover         = BACKUP
query_cache_limit   = 1M
query_cache_size        = 16M
log_error                = /var/log/mysql/error.log
expire_logs_days    = 10
max_binlog_size         = 100M
[mysqldump]
quick
quote-names
max_allowed_packet  = 16M
[mysql]
[isamchk]
key_buffer      = 16M
!includedir /etc/mysql/conf.d/

I tried changing the bind-address line above to 0.0.0.0, 127.0.0.0 and 127.0.1.1 (this one because I have a 127.0.1.1 foo line in my /etc/hosts where foo is my VM's hostname) and 10.1.1.213 which is the actual internal IP of the machine on my network. None of them made any difference. I also tried commenting out the bind-address line for good measure and ditto.

My system details:

$ cat /etc/issue
Ubuntu 14.04.1 LTS \n \l

$ dpkg -s mysql-server | grep version
Version: 5.5.38-0ubuntu0.14.04.1