Resolvido:
Em Fontes de Software, rótulo Outro Software, havia um repositório chamado "Parceiros Canônicos adicionados pela Central de Software principal". Desmarquei essa opção porque ainda há outra fonte chamada "Software de Parceiros Canônicos da Canonical para seus parceiros".
Eu também mudei para o servidor do USA (eu estava no main), como eu vi que parece ter alguma coisa a ver com o repositório do Skype no servidor principal.
Isso parece ter resolvido o problema.