Eu não uso o Deja Dup, mas eu uso duplicidade. (Praticamente o backend para DD).
Você criptografou os arquivos com uma chave privada? Se assim for, você precisa dessa chave secreta para descriptografar os arquivos. Experimente:
gpg --import /path/to/key/key.key