Eu suponho que isso seja depois de um comando apt-get
? se sim, execute apt-get update
e certifique-se de que não haja erros 404 ou de outros downloads na lista antes de tentar novamente.
se você estiver usando a loja de software do Ubuntu (argh), clique em qualquer botão chamado refresh ... ok, acabei de marcar. não há nenhum ... então ignore esta linha.
se você estiver usando GUI, execute o Software Updater. ele atualizará a lista automaticamente. e depois abra a loja de software e tente novamente o que você estava tentando.