Você deve levar algum tempo para realmente ler a mensagem, pois não é um erro. Tente isso:
sudo service mysql start
Alguma alteração na saída?
A razão para isto é que o sysvinit tradicional foi substituído por Upstart / Services no Ubuntu 6.10. No entanto, uma grande quantidade de pacotes ainda usa a antiga maneira sysvinit, que foi deixada no lugar para compatibilidade com versões anteriores. A maior diferença, além de ter que usar outro comando, é que o upstart é orientado a eventos, ao contrário do sysvinit, que é um gerenciador de serviços sequencial.