L'auteur de Deja Dup a publié https://wiki.gnome.org/Apps/DejaDup/PassphraseProblems2019 dans lequel il décrit les raisons possibles dues à des bugs dans les versions précédentes de Deja Dup et des bugs dans la duplicité sous-jacente.
TL;DR est que vous avez peut-être entré un mauvais mot de passe lorsqu'il vous a été demandé. Malheureusement, au moins les versions antérieures de duplicity ne vérifient pas si la phrase de passe passée correspond à celle utilisée dans les sauvegardes précédentes.
Dans mon cas, les fichiers de sauvegarde les plus récents ont été cryptés avec une mauvaise phrase de passe. Le document en question fournit une commande pour vérifier cela. J'ai donc simplement supprimé ces fichiers et relancé la sauvegarde.
Ubuntu 18.04 utilise Deja Dup version 37.0 qui contient toujours ce bogue. Selon le document lié ci-dessus, le bogue est corrigé à partir de la version 39.1.