No daba ninguna información adicional útil en el log. Lo resolví ejecutando esto:
chmod 1777 /tmp
Visto aquí:
http://www.linuxquestions.org/questions/ubuntu-63/mysql-start-job-failed-to-start-4175503017/
En otros sitios de internet dicen que se resuelve reinstalando todo.