Eu também estava enfrentando o mesmo problema, no Ubuntu 12.10i não foi possível abrir o centro de software.
A solução para meu problema foi como direitos de nível de root que acabei de atualizar o apt-get:
apt-get update
após a atualização, abri o centro de software e consegui abrir.