Primeiramente, verifique se sua conexão com a internet está funcionando. Você consegue navegar em sites em seu navegador quando esse erro ocorre?
Pode ser necessário atualizar os metadados do pacote. Feche o Centro de Software. Abra o Unity Dash (ícone superior no dock) e digite "Update Manager". Abra o Gerenciador de Atualizações e clique em "Verificar". Aguarde a conclusão (isso precisa de uma conexão com a Internet), feche-a, abra o Centro de Software e tente instalar. Observe que a instalação das atualizações sugeridas pelo Update Manager não é necessária para isso (mas é recomendada em geral).
Como alternativa, em vez do gerenciador de atualizações, você também pode fazer sudo apt-get update
em um terminal.