Vc andou instalando algum PPA ou programa que não faz parte do repositório oficial do Ubuntu?
Vc já reinstalou várias vezes esses aplicativos, a não funcionou, pode ser problema de alguma dependência que é comum aos dois. Eu estou vendo aqui pelo Synaptic, e percebi que os dois tem em comum o python. Tem também alguns outros pacotes em comum. Quando vc desinstala e instala novamente a Central de Programas e o programa de Update, essas dependências não são alteradas, pois o resto do sistema também depende de um pacote ou outro. Instale o Synaptic (sudo apt-get install synaptic) e vá dando uma olhada, se tiver paciência. Esse Synaptic também serve para instalar programas e vc pode atualizar o sistema por ele também. Aí vc vai vendo os pacotes em comum, e vai pedindo para reinstalar, um por um.
Esse problema que vc teve não é comum, nenhum programa para de funcionar assim do nada. Ou você andou instalando programas ou atualizando o sistema com auxilio de PPA's (repositórios de terceiros, não suportado oficialmente pela Canonical) ou até mesmo baixando direto e instalando (e isso pode ter contribuido para o problema, deve ter alterado algum pacote essencial), ou seu HD está com problemas e está falhando (já aconteceu comigo, alguns programas paravam de responder, sistema congelava, teve vez de eu atualizar o sistema e conseguir dar boot depois somente com versão do kernel antigo, acontecia uns negócios que não tinha explicação).