Você deve fazer algumas leituras . Então você vai entender que alguns links especiais são criados nos diretórios de runlevel, alguns são para iniciar o mysql e alguns são para parar o mysql ao sair do runlevel (como quando você está parando a máquina).
A melhor solução é:
- Reinstale os links mysql
update-rc.d mysql defaults
(acho que você pode precisar de um-f
também) - Desabilite corretamente o serviço mysql
update-rc.d mysql disable
(também, você pode precisar de um-f
Isso permitirá que o K vincule e renomeie os links S. Espero que você tenha lido para entender o que esta última parte significa.