Na maioria das vezes, é por causa do último ponto listado: você tem alguns PPAs habilitados que não podem ser atualizados.
Desative todos os PPAs que você instalou manualmente e execute a atualização. Após a atualização, reative-os.
Isso é feito com mais facilidade por meio do utilitário "Software e atualizações".