Verifique no Ubuntu Software Center ou no Gerenciador de Pacotes Synaptic. Os programas instalados estão marcados. Se você usar o Synaptic (é bastante rápido), clique no botão de pesquisa em vez de usar a caixa de pesquisa padrão (é buggy). Você pode reinstalar um pacote mesmo que ele seja exibido como instalado.
Também execute sudo apt-get autoremove && sudo apt-get update
antes disso.
Espero que isso ajude.