Você precisa executar primeiro apt-get update
Da página man:
update
update is used to resynchronize the package index files from their sources. The indexes of available
packages are fetched from the location(s) specified in /etc/apt/sources.list. For example, when using a
Debian archive, this command retrieves and scans the Packages.gz files, so that information about new and
updated packages is available. An update should always be performed before an upgrade or dist-upgrade.
Please be aware that the overall progress meter will be incorrect as the size of the package files cannot
be known in advance.
Portanto, para que o APT obtenha o banco de dados de pacotes e atualize Recomenda-se fazer primeiro apt-get update