Antes de digitar sudo apt-get install
, você digitou sudo apt-get update
primeiro?
Eu geralmente tenho esse problema em um VPS que eu uso, depois de uma nova instalação eu tenho que digitar o apt-get update e só então eu posso instalar pacotes.