Vá para SystemSettings - > Software e atualizações para a guia "Ubuntu Software". Tente definir o campo "Baixar de" para "Servidor Principal". Eu tive problema semelhante com o meu servidor predefinido não está funcionando sempre. Você também pode selecionar a opção "Other .." em vez de "Main Server". Será aberta uma janela onde você poderá clicar em "Selecionar melhor servidor" e deixar o Ubuntu encontrar a melhor / mais próxima / mais rápida opção.