Você pode não ter removido o pacote corretamente ou apt-get foi interrompido ao remover o pacote. Primeiro, sugiro executar o seguinte para processar as operações pendentes:
apt-get -f install
Quando isso for feito, use autoremove para garantir que não haja lixo no caminho:
apt-get autoremove
Em seguida, remova seu pacote completamente:
apt-get remove --purge [package name]