After a restart, mysql won't start. sudo service mysql start gives start: Job failed to start and the logs are empty, so I have no idea where to start. I'm pretty sure permissions problems are taken care of.

Edit:
All disks have at least 1G of space and sh -x /etc/init.d/mysql start gives me:

+ set -e
+ basename /etc/init.d/mysql
+ INITSCRIPT=mysql
+ JOB=mysql
+ [ mysql = upstart-job ]
+ [ -z start ]
+ COMMAND=start
+ shift
+ [ -z  ]
+ ECHO=echo
+ echo Rather than invoking init scripts through /etc/init.d, use the service(8)
Rather than invoking init scripts through /etc/init.d, use the service(8)
+ echo utility, e.g. service mysql start
utility, e.g. service mysql start
+ echo

+ echo Since the script you are attempting to invoke has been converted to an
Since the script you are attempting to invoke has been converted to an
+ echo Upstart job, you may also use the start(8) utility, e.g. start mysql
Upstart job, you may also use the start(8) utility, e.g. start mysql
+ grep -q  start/
+ status mysql
+ [ -z  ]
+ [ start = stop ]
+ [ -n  ]
+ start mysql
start: Rejected send message, 1 matched rules; type="method_call", sender=":1.105" (uid=1000 pid=3208 comm="start mysql ") interface="com.ubuntu.Upstart0_6.Job" member="Start" error name="(unset)" requested_reply="0" destination="com.ubuntu.Upstart" (uid=0 pid=1 comm="/sbin/init")