Hi @jlxb,
sorry to hear you are having problems, I don't have an answer for regarding Deja Dup but offer a few of my own back-up suggestions instead (most likely not what you want but there you go!).
I copy all my important files to an external USB drive and also to other reserve partitions on my computer.
If I need to do a new install, I use the "Something else method" which keeps all my settings and data intact and only leaves for me to re-install all my fav apps which I do with a pre-written "Meta Terminal Command" (sudo apt-get install blah blah blah blah etc).
I don't rely on back-up apps for the very reasons you have stated above!.