Acho que o Centro de software não está indexado corretamente / não está funcionando corretamente nos dias de hoje. Não me cite, eu não sou um especialista. Eu nunca usei mesmo assim. Eu uso synaptic package manager
para gerenciar meus pacotes de software, por que não tentar e ver como você se sai.
sudo apt-get install synaptic
Ele aparecerá no seu menu principal, execute-o e insira o que quiser na caixa de pesquisa. Selecione e instale pacotes.