sudo apt-get check
é seu amigo. :)
Da página do manual:
checkcheck é uma ferramenta de diagnóstico; atualiza o cache do pacote e verifica se há dependências quebradas
Para verificações mais finas (meio-configuradas, etc.), você pode tentar sudo dpkg -C
:
-C, --audit
Procura pacotes que foram instalados apenas parcialmente no seu sistema. dpkg
sugerirá o que fazer com eles para que eles funcionem.