Hola, yo uso youtube-dl pero lo actualizo manualmente, independiente del sistema de paquetes, ya que lo actualizan constantemente.
La última versión disponible en github es la 2020.01.24 (anteayer), pero en el repositorio de bullseye la última es la 2019.09.28.
Yo tuve que actualizarlo anteayer porque dejó de funcionarme también.
Para actualizarlo sólo tienes que usar el comando 'youtube-dl -U' con permisos de superusuario de vez en cuando cuando deje de funcionar, o esperar a que lo actualicen en el repo de debian, supongo.
Un saludo.
P.D: es la primera vez que uso la lista, así que agradezco que me corrijáis si hago algo mal (o si me equivoco).
Actualizo: he vuelto a mandar el correo porque creo que la primera vez he respondido sólo a Rubén, y en la web de la lista no aparece mi mensaje. Perdón por las molestias.