As of today and revision bzr1048 installed from the duplicity daily-ppa, this problem persists on two unicorn, 64bit machines with fresh installs and language set to German respectively. Here is what I did:

I have an example directory with the path /home/paul/Musik/Clueso/Gute Musik/ that I wanted to backup via deja dup and that contains some files with and some files without special characters. What's worth noticing is that deja-dup seemingly shows how duplicity handles files with special characters different from such files without special characters.

This is the log from the deja-dup window:
[Einlesen is German and means "Reading" or "Indexing"]
[Sichern is German and means "Backing Up"]

Einlesen: /home/paul/Musik/Clueso/Gute Musik/.mediaartlocal/album-4e2e697e4e8f7556783434043ce052fe-7bad226fa0d8ca5da1405e4036652062.jpeg.gz
Einlesen: /home/paul/Musik/Clueso/Gute Musik/.mediaartlocal/album-70dd1a377d1e83914185be0f10e7cb47-7bad226fa0d8ca5da1405e4036652062.jpeg.gz
Einlesen: /home/paul/Musik/Clueso/Gute Musik/.mediaartlocal/album-84036bb3393f96f3e67553cf7361aacc-7bad226fa0d8ca5da1405e4036652062.jpeg.gz
Einlesen: /home/paul/Musik/Clueso/Gute Musik/.mediaartlocal/album-97f7883864ed3e64087ef4bb33844b17-7bad226fa0d8ca5da1405e4036652062.jpeg.gz
Einlesen: /home/paul/Musik/Clueso/Gute Musik/.mediaartlocal/album-b5af0a75d8062a26edc60a3841d2e1a7-7bad226fa0d8ca5da1405e4036652062.jpeg.gz
Einlesen: /home/paul/Musik/Clueso/Gute Musik/.mediaartlocal/album-b6c6d51a1e55f412332925a9f67d2b6e-7bad226fa0d8ca5da1405e4036652062.jpeg.gz
Einlesen: file:///home/paul/Musik/Clueso/Gute%20Musik/01%20Clueso%20mit%20J%FCrgen%20Kerth%20Band%20-%20Nacht%20unterwegs.mp3
Einlesen: /home/paul/Musik/Clueso/Gute Musik/02 Clueso - Das Level.mp3
Einlesen: /home/paul/Musik/Clueso/Gute Musik/03 Clueso - Uh Girl.mp3
Einlesen: /home/paul/Musik/Clueso/Gute Musik/04 Clueso - Gute Musik.mp3
Einlesen: /home/paul/Musik/Clueso/Gute Musik/05 Clueso mit Delhia - Dort wo du wohnst.mp3
Einlesen: file:///home/paul/Musik/Clueso/Gute%20Musik/06%20Clueso%20-%20Es%20wird%20hei%DF.mp3
Einlesen: /home/paul/Musik/Clueso/Gute Musik/07 Clueso mit Steer-M - Love the People.mp3
Einlesen: /home/paul/Musik/Clueso/Gute Musik/08 Clueso - Kalter Kaffee.mp3
Einlesen: /home/paul/Musik/Clueso/Gute Musik/09 Clueso - Bescheid.mp3
Einlesen: file:///home/paul/Musik/Clueso/Gute%20Musik/10%20Clueso%20-%20Vier%20kleine%20W%E4nde.mp3
Einlesen: /home/paul/Musik/Clueso/Gute Musik/11 Clueso - City-Pizza-Express.mp3
Einlesen: /home/paul/Musik/Clueso/Gute Musik/12 Clueso - Pizzaschachteln.mp3
Einlesen: file:///home/paul/Musik/Clueso/Gute%20Musik/13%20Clueso%20-%20Wie%20hei%DFt'n%20du_.mp3
Einlesen: /home/paul/Musik/Clueso/Gute Musik/14 Clueso - Wart mal.mp3
Einlesen: /home/paul/Musik/Clueso/Gute Musik/15 Clueso - Vergessen ist so leicht.mp3
Einlesen: /home/paul/Musik/Clueso/Gute Musik/16 Clueso mit Tim Neuhaus - Fanpost.mp3
Einlesen: /home/paul/Musik/Clueso/Gute Musik/17 Clueso mit Blumentopf - Egal wo.mp3
Einlesen: /home/paul/Musik/Clueso/Gute Musik/18 Clueso - Ich geh heim.mp3
Einlesen: /home/paul/Musik/Clueso/Gute Musik/19 Clueso - Herz Boom Boom.mp3
Einlesen: /home/paul/Musik/Clueso/Gute Musik/20 Clueso - Vorspiel.mp3
Einlesen: /home/paul/Musik/Clueso/Gute Musik/21 Clueso - Kein Bock zu geh'n.mp3
Sicherung läuft: /home/paul/Musik/Clueso/Gute Musik/.mediaartlocal/album-4e2e697e4e8f7556783434043ce052fe-7bad226fa0d8ca5da1405e4036652062.jpeg.gz
Sicherung läuft: /home/paul/Musik/Clueso/Gute Musik/.mediaartlocal/album-70dd1a377d1e83914185be0f10e7cb47-7bad226fa0d8ca5da1405e4036652062.jpeg.gz
Sicherung läuft: /home/paul/Musik/Clueso/Gute Musik/.mediaartlocal/album-84036bb3393f96f3e67553cf7361aacc-7bad226fa0d8ca5da1405e4036652062.jpeg.gz
Sicherung läuft: /home/paul/Musik/Clueso/Gute Musik/.mediaartlocal/album-97f7883864ed3e64087ef4bb33844b17-7bad226fa0d8ca5da1405e4036652062.jpeg.gz
Sicherung läuft: /home/paul/Musik/Clueso/Gute Musik/.mediaartlocal/album-b5af0a75d8062a26edc60a3841d2e1a7-7bad226fa0d8ca5da1405e4036652062.jpeg.gz
Sicherung läuft: /home/paul/Musik/Clueso/Gute Musik/.mediaartlocal/album-b6c6d51a1e55f412332925a9f67d2b6e-7bad226fa0d8ca5da1405e4036652062.jpeg.gz
Sicherung läuft: file:///home/paul/Musik/Clueso/Gute%20Musik/01%20Clueso%20mit%20J%FCrgen%20Kerth%20Band%20-%20Nacht%20unterwegs.mp3
Sicherung läuft: /home/paul/Musik/Clueso/Gute Musik/02 Clueso - Das Level.mp3
Sicherung läuft: /home/paul/Musik/Clueso/Gute Musik/03 Clueso - Uh Girl.mp3
Sicherung läuft: /home/paul/Musik/Clueso/Gute Musik/04 Clueso - Gute Musik.mp3
Sicherung läuft: /home/paul/Musik/Clueso/Gute Musik/05 Clueso mit Delhia - Dort wo du wohnst.mp3
Sicherung läuft: file:///home/paul/Musik/Clueso/Gute%20Musik/06%20Clueso%20-%20Es%20wird%20hei%DF.mp3
Sicherung läuft: /home/paul/Musik/Clueso/Gute Musik/07 Clueso mit Steer-M - Love the People.mp3
Sicherung läuft: /home/paul/Musik/Clueso/Gute Musik/08 Clueso - Kalter Kaffee.mp3
Sicherung läuft: /home/paul/Musik/Clueso/Gute Musik/09 Clueso - Bescheid.mp3
Sicherung läuft: file:///home/paul/Musik/Clueso/Gute%20Musik/10%20Clueso%20-%20Vier%20kleine%20W%E4nde.mp3
Sicherung läuft: /home/paul/Musik/Clueso/Gute Musik/11 Clueso - City-Pizza-Express.mp3
Sicherung läuft: /home/paul/Musik/Clueso/Gute Musik/12 Clueso - Pizzaschachteln.mp3
Sicherung läuft: file:///home/paul/Musik/Clueso/Gute%20Musik/13%20Clueso%20-%20Wie%20hei%DFt'n%20du_.mp3
Sicherung läuft: /home/paul/Musik/Clueso/Gute Musik/14 Clueso - Wart mal.mp3
Sicherung läuft: /home/paul/Musik/Clueso/Gute Musik/15 Clueso - Vergessen ist so leicht.mp3
Sicherung läuft: /home/paul/Musik/Clueso/Gute Musik/16 Clueso mit Tim Neuhaus - Fanpost.mp3
Sicherung läuft: /home/paul/Musik/Clueso/Gute Musik/17 Clueso mit Blumentopf - Egal wo.mp3
Sicherung läuft: /home/paul/Musik/Clueso/Gute Musik/18 Clueso - Ich geh heim.mp3
Sicherung läuft: /home/paul/Musik/Clueso/Gute Musik/19 Clueso - Herz Boom Boom.mp3
Sicherung läuft: /home/paul/Musik/Clueso/Gute Musik/20 Clueso - Vorspiel.mp3
Sicherung läuft: /home/paul/Musik/Clueso/Gute Musik/21 Clueso - Kein Bock zu geh'n.mp3


Now after the backup is done, I deleted the tracks no. 05 (a file without special characters) and a track no. 06 (a file with special characters) and in nautilus right clicked to restore files. After it's done looking for missing files it lists track no 05 and track no 06, but also all the other files with special characters in the directory as missing, despite the fact, that I actually only deleted files 05 and 06. 

After clicking restore, file 05 is being restored, while for file 06 an empty directory is being created named "06 Clueso - Es wird hei�.mp3 (ungültige Kodierung)" 
[ungültige Kodierung is German and means "invalid encoding"].

Eventually the deja-dup window shows me an error saying

»file:///home/paul/Musik/Clueso/Gute%20Musik/06%20Clueso%20-%20Es%20wird%20hei%DF.mp3« konnte nicht wiederhergestellt werden: Datei wurde in der Sicherung nicht gefunden.
["file.... couldn't be restored: The file was not found in the backup"].

That's a pretty unfortunate situation, as my backup is useless at least for a folder or file that contains special characters. That's especially drastic for people who backup their home directors but have a special character in their name - Imagine the hard drives of Jérôme, Günther, Abigaíl or František break and their whole backup is as useful as a bag of stones.