Você já tentou dpkg --purge PACKAGENAME ? Isso deve remover o pacote com todos os seus arquivos de configuração.
Eu acidentalmente quebrei a instalação do apache2, e queria saber se eu poderia remover completamente o apache2 e tudo relacionado a ele, e depois reinstalá-lo completamente a partir do zero?
Você já tentou dpkg --purge PACKAGENAME ? Isso deve remover o pacote com todos os seus arquivos de configuração.