Eu tive o mesmo problema no Ubuntu 17.04. Depois que eu corri o comando:
sudo apt-cache policy deja-dup duplicity
Eu vi na saída do terminal que a duplicidade não está instalada. Então eu instalei com o apt.
sudo apt-get install duplicity
E o erro foi resolvido com sucesso. Espero que ajude você também.