As pointed out by Luca on irc (thanks!) Debian's

/usr/share/dbus-1/system.d/org.freedesktop.locale1.read-only.conf

prevents changing the locale via localed. This is unexpected and
deviates from upstream behavior. Would be great if this could be
enabled at some point as without it gnome-control-center and other
apps can't set the user's locale.

Cheers,
 -- Guido