Use dpkg -S para descobrir de qual pacote o arquivo /usr/lib/libmysqlclient.so.16 é, não acho que seja de libmysqlclient-dev , mas de libmysqlclient , o comando dpkg -S é para verificar sua origem ...
Desinstale e reinstale o pacote resultante. Depois de reinstalar, execute ldconfig para forçar seu sistema a reconstruir as estruturas de links simbólicos em /usr/lib .
Editar
Fiz uma instalação rápida de 10.04 para verificar. /usr/lib/libmysqlclient.so.16 vem do pacote libmysqlclient16 . Então, voltando à sua pergunta: Não, o pacote libmysqlclient-dev não contém as bibliotecas que você está procurando.
Desinstalar:
sudo apt-get purge libmysqlclient16
Instalar:
sudo apt-get install libmysqlclient16
A instalação do pacote também deve acionar uma execução de ldconfig .