Короче, решил, хотя данная конструкция больше карточный домик напоминает:
addgroup bgusers
chown root:bgusers /usr/bin/gnome-appearance-properties
chmod 754 /usr/bin/gnome-appearance-properties
usermod -a -G bgusers $rightuser
Где rightuser=пользователь, которому разрешено менять обои.
В итоге, хоть и пункт "Изменить фон рабочего стола" не ушла, зато апплет теперь не запускается у тех юзверей, которым ето не разрешено.