А у меня так:
Попробуйте сделать классический поиск я всегда это советую, ну типа «от печки», есть такая идиома в русском языке…
sudo updatedb # обновить базу данных
locate -cie "*youtube-dl*"
locate -ie "*youtube-dl*"
Вот у меня всего 6 позиций, но интерес представляет только эта
/usr/local/bin/youtube-dl
Я забыл откуда я брал этот совет устанавливать (« Ответ #5 : Сегодня в 14:29:37 ») , но по-моему непосредственно с их сайта…
Посмотрите если после удаления ничего с названием
youtube-dl не покажется, пробуйте устанавливать.
У меня xUbuntu 20.04, но думаю это не важно.