Primeiro, você realmente não deve usar o comando kill para parar seu serviço mysql. Use o serviço:
sudo service mysql stop
sudo service mysql start
Não tenho certeza do que o mysql-cluster-client-5.1, além do óbvio, é um cliente mysql projetado para trabalhar em clusters (pense em um servidor com muitos cpus).
Quanto ao motivo pelo qual o mysql-client-core foi removido, meu palpite é que ele foi atualizado para que o pacote antigo fosse removido ou que outro pacote fornecendo a mesma funcionalidade fosse instalado em seu lugar. Se o seu mysql puder ser controlado OK com os comandos que eu dei acima, eu não me preocuparia com isso.