Após uma nova instalação, você sempre precisará executar um sudo apt-get update para atualizar sua lista de pacotes usando os arquivos /etc/apt/sources.list e /etc/apt/sources.list.d/* .
Isso atualiza a lista de pacotes e ajuda a saber onde cada pacote mencionado em sudo apt-get install <package_name> deve ser obtido.
Portanto, antes de fazer um sudo apt-get install <package_name> na nova instalação padrão (padrão no sentido de que não é uma instalação remasterizada - que pode ou não exigir necessariamente uma atualização), você precisa fazer uma sudo apt-get update .