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.