Eu tive o mesmo problema. Eu consegui trabalhar alterando a linguagem do sistema para o inglês. Acho que o problema é que as descrições do programa não estão disponíveis no meu idioma.
O título já diz tudo. Eu atualizei sem problemas de 15.10 para 16.04 LTS, o ícone do Ubuntu Software permaneceu o mesmo, se eu abri-lo eu recebo a nova versão do GNOME, mas quando eu procuro por alguns aplicativos (como o GIMP, ou VLC Player) eu recebo "sem aplicação encontrado ".
Estranho, não é?
Eu tive o mesmo problema. Eu consegui trabalhar alterando a linguagem do sistema para o inglês. Acho que o problema é que as descrições do programa não estão disponíveis no meu idioma.