Вам нужно сначала запустить apt-get update
Из man page:
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.
Итак, для того, чтобы APT получил базу данных пакетов и обновил ее, рекомендуется сначала выполнить apt-get update
Ответ оказывается связанным с другим вопросом, я задал -компостирование. Чтобы исправить в KDE, мне нужно было отключить компостирование, нажав:
CtrlShiftF12