Isso geralmente é causado pela falha de um de seus repositórios de software (como um PPA que não funciona mais).
Tente isso em um terminal:
sudo apt-get update
Você deve ver uma mensagem sobre um erro de repositório. Se você não vir a mensagem, percorra toda a saída até encontrá-la.
Depois de encontrar o culpado, desative-o em Fontes de software e atualize-o novamente. A mensagem deve desaparecer.