Tente instalar o antigo centro de software na linha de comando:
sudo apt install software-center
Ou tente instalar o synaptic
sudo apt install synaptic
Após a atualização para o Ubuntu 16.04, tentei usar o novo centro de software que veio junto, mas achei que tinha alguns problemas. Um, ele não detectou todos os aplicativos que eu tinha instalado anteriormente e dois, sempre que eu tentei instalar um novo software com ele, um novo ícone no lançador (dizendo "Aguardando para instalar") aparece, mas nenhum progresso é feito e o ícone está preso no lançador.
No entanto, não encontro nenhum desses problemas no antigo Centro de Software. Alguém sabe porque isso pode ser?
Tente instalar o antigo centro de software na linha de comando:
sudo apt install software-center
Ou tente instalar o synaptic
sudo apt install synaptic
Resolvi esse mesmo problema usando "verificar se há atualizações" no menu "Sobre este computador" - > "Detalhes" encontrado na área de menu superior direita da área de trabalho.
Tente baixar e instalar o antigo Centro de Software do novo Centro de Software. Basta digitar o nome no novo Centro de Software, localizá-lo e usá-lo.