Isso pode ser devido a um certificado corrompido ou antigo que foi baixado.
Um certificado é usado para autenticar solicitações da web que qualquer um dos comandos do apt-get usa - link
Um relatório similar foi feito através do UbuntuForums para o webupd8 PPA.
A solução é reproduzida aqui:
sudo rm -rf /usr/share/ca-certificates
sudo apt-get --reinstall install ca-certificates
O que isto faz é remover à força qualquer certificado instalado no seu computador. Em seguida, os certificados ca padrão são reinstalados para preencher a lista de certificados corretamente.