Tenia un equipo con Ubuntu 15.10 y al actualizarlo a 16.04 MySQL dejo de funcionar, para repararlo seguí los siguientes pasos.
Primero hay que hacer un respaldo de la carpeta de bases de datos /var/lib/mysql y de la de configuraciones /etc/mysql.
Desinstalar MySQL con el siguiente comando.
Reinstalar MySQL.
Iniciar MySQL.