Эта проблема со дня выхода 22.04.
Если ты установишь все нужные пакеты в первые 15 мин после установки системы, то всё установится и потом будет обновляться.
Если ты только профукаешь время больше и начнёшь устанавливать что-либо позже, то будет вылазить, что не найден кандидат на установку.
Но вручную скачивание этих же пакетов с хранилища Canonical - packages.ubuntu.com и их установка например через gDebi или:
sudo dpkg -i /путь/к/пакету/пакет.deb
будет устанавливать, но при возникновении ошибки о зависимости от того или иного пакет придётся докачивать и устанавливать также и их.
И обновления будут частичными.
Что-то будет обновляться, а что-то будет с такими ошибками, как у тебя и не только у тебя.
У меня тоже самое.
Решения нет, увы!
Ходят слухи на просторах, связано это только с российскими IP в виду, сами понимаете чего...
Такая вот дискриминация...