Eu tive o mesmo problema. Para mim, removendo o cache em ~/.cache/software-center e abrindo o Centro de Software, fiz o trabalho.
Basta abrir sua pasta pessoal, pressionar ctrl + h para revelar arquivos ocultos, abrir .cache e excluir a pasta software-center (ou, mais seguro, renomeá-la, por exemplo, para software-centerDeleted ). Parece que não são necessárias permissões de root.