Algumas coisas para tentar.
- verifique se os pacotes ainda estão disponíveis
sudo apt list | egrep software-center
lubuntu-software-center / xenial, xenial 0.0.10-0ubuntu2 em todo o mundo
software-center / xenial, xenial 16.01 + 16.04.20160420 todos os
software-center-aptdaemon-plugins / xenial, xenial 0.1.6build1 todos os
ubuntu-kylin-software-center / xenial, xenial 1.3.10 todos
- se não, tente obter os pacotes
sudo apt-get *software-center*
Veja se isso ajuda.
Eu executei os comandos acima na minha instalação do 16.04 para ver quais pacotes de "software-center" estão instalados por padrão. Eu fiz um teste rápido para baixar os pacotes para um diretório tmp, e todos eles baixaram.
tonym@familypc:~/tmp$ ls
lubuntu-software-center_0.0.10-0ubuntu2_all.deb
software-center_16.01+16.04.20160420_all.deb
software-center-aptdaemon-plugins_0.1.6build1_all.deb
ubuntu-kylin-software-center_1.3.10_all.deb