Aparentemente, esta foi uma questão há dois anos (2011) e é novamente uma questão (2013). Estou executando o Ubuntu 13.04 e o gerenciador de atualização não será atualizado devido a um erro de "atualização não confiável". A mensagem de erro real diz algo como "Esta atualização exigirá instalação de fontes não confiáveis" e os botões disponíveis são "configurações" e "ok".
Normalmente, se alguém avisar você e você disser "Ok", a ação ocorrerá. Não é assim aqui. "Ok" simplesmente fecha o gerenciador de atualização. 'settings' abre a janela de diálogo de configurações, sem indicação específica de como corrigir o problema.
Eu verifiquei o site liberiangeek mencionado por aneeshep, executei o comando sudo recomendado lá, e o comando update correu bem, não encontrei nenhuma chave pública ausente.
Em seguida, executei o Ubuntu Software Updater, e ele ainda encontrou 81,3 MB de downloads, e a lista parece ser a mesma: algumas atualizações de segurança, algumas outras atualizações e uma longa lista de atualizações de base do Ubuntu.
Quando clico em "Instalar agora" e digito minha senha, o atualizador faz o download de vários pacotes, instala-os e me diz "O software neste computador está atualizado"
YAY! Finalmente! (Ele também menciona uma atualização para 13.10 está disponível ...)
Então: instruções relevantes são:
A partir de um terminal (tipo Applications > system > > XTerm)
sudo apt-get update
Após este comando terminar, feche o terminal com "exit".
Em seguida, tente atualizar seu sistema, ele deve funcionar.