The issue is the OpenDesktop category that the authors of the deja-dup put the settings program into. The new version appears to only have one .desktop file. You want to edit /usr/share/applications/org.gnome.DejaDup.desktop with your favourite editor (you'll need to be root and add Settings to the Categories, and also replace X-GNOME-Utilities with X-GNOME-SystemSettings. I have opted to keep the original Categories line by hashing it out, so that my file looks like this:
$ cat /usr/share/applications/org.gnome.DejaDup.desktop
[Desktop Entry]
Version=1.1
X-Ubuntu-Gettext-Domain=deja-dup
Name=Backups
Comment=Change your backup settings
Icon=org.gnome.DejaDup
Exec=deja-dup
StartupNotify=true
DBusActivatable=true
Type=Application
#Categories=Utility;Archiving;GNOME;GTK;X-GNOME-Utilities;
Categories=Settings;Utility;Archiving;GNOME;GTK;X-GNOME-SystemSettings;
# Translators: Add whatever keywords you want in your language, separated by semicolons
# These keywords are used when searching for applications in dashes, etc.
Keywords=déjà;deja;dup;
X-GNOME-UsesNotifications=true
Actions=backup;
[Desktop Action backup]
Name=Back Up
Exec=deja-dup --backup
$
[Desktop Entry]
Version=1.1
X-Ubuntu-Gettext-Domain=deja-dup
Name=Backups
Comment=Change your backup settings
Icon=org.gnome.DejaDup
Exec=deja-dup
StartupNotify=true
DBusActivatable=true
Type=Application
#Categories=Utility;Archiving;GNOME;GTK;X-GNOME-Utilities;
Categories=Settings;Utility;Archiving;GNOME;GTK;X-GNOME-SystemSettings;
# Translators: Add whatever keywords you want in your language, separated by semicolons
# These keywords are used when searching for applications in dashes, etc.
Keywords=déjà;deja;dup;
X-GNOME-UsesNotifications=true
Actions=backup;
[Desktop Action backup]
Name=Back Up
Exec=deja-dup --backup
$
Note the hashed-out Categories= and the new Categories=