Eu responder-lhe em geral: quando você vê um tal impasse pode tentar algumas coisas, todos eles podem, eventualmente, causar-lhe problemas, então você provavelmente deve usá-los apenas temporariamente
.1) Tente remover pacotes ofensivos . No seu caso, são mdns e plymouth. Eu não sei mdns (se ninguém depende disso você pode ter sorte para removê-lo, mas você pode perder algumas funcionalidades, então reinstalá-lo mais tarde); removendo plymouth você perderia animação de inicialização e outras coisas, você pode não querer fazê-lo.
2) tentar verificar os arquivos /etc/init.d/ e tente remover "$ all" de dependências (o bloco comentou sobre o topo do arquivo), especialmente a partir Obrigatório - linhas. * Nesse caso, eu verificaria /etc/init.d/mdns e removeria "$ all" da parte inicial. Isso fará com que o mdns comece mais tarde, o que - por suposição instruída - não deve quebrar o seu sistema (mas pode, com uma probabilidade muito baixa, ainda não ter garantias). Geralmente "$ all" não é justificado e pode ser um bug de empacotamento. Possivelmente atualizar até mesmo corrige isso para você.
Você pode testá-lo executando "insserv -n" manualmente.