Eu tenho o mesmo problema usando o Ubuntu 16.04, então eu instalo o Centro de software do Ubuntu v 15.12 e ele funciona.
sudo apt install software-center
e depois
software-center
finalmente recebo o ícone ao lado. Isso resolve o problema por enquanto.