Os erros "Não encontrados" dos repositórios oficiais são geralmente um sinal de que sua lista de pacotes locais está desatualizada. Se esta for uma instalação muito nova (como o seu post sugere), isso é ainda mais provável. O instalador realmente precisa fazer isso, mas lá vai você.
Execute um sudo apt-get update
(ou use um gerenciador de pacotes gráfico para atualizar) e você deve descobrir que esse tipo de erro evapora.