Parece um problema de biblioteca para mim.
Tente executar o ldconfig.
Se isso não ajudar, tentarei identificar com qual pacote o cliente mysql vem, remover e reinstalar esse pacote. Eu não estou familiarizado com os pacotes debian para saber, mas no cliente redhat o mysql tem seu próprio pacote, separado do mysql-server e do mysql-common.
Tente também identificar de que pacote libmysqlclient.so.16 vem e desinstalar / reinstalar o pacote.
Você também não mudou as arquiteturas, por exemplo mudou de 32 para 64 bits? Nesse caso, você pode querer verificar qual o arco do binário mysql (use o comando file) e certifique-se de ter as bibliotecas de archives corretas instaladas.