Dear Rob,
It is not possible to set a custom theme using only the menu bar and
without setting it by hand in init file. The theme will be applied but
after restarting Emacs, it won't be loaded automatically.
This bug only applies to the themes which are not shipped with Emacs but
can be installed from Debian repos.
These are steps to reproduce:
1. Install Emacs from Debian repos
($ sudo apt install emacs)
2. Install an Emacs theme from Debian repos. For instance Monokai
($ sudo apt install elpa-monokai-theme)
3. Go to Options > Customize Emacs > Custom Themes
4. Choose monokai
5. Click on Save Theme Settings
6. Restart Emacs
Workaround:
Adding package initialize and loading the theme manually solves the bug.
(package-initialize)
(load-theme 'monokai t)
Cheers,
Salman