Maybe [1] has the missing clue. If your mentry is under the Advanced
menu, you need to use a special syntax.
I just tried the following
1. Set GRUB_DEFAULT=saved, as you did and ran update-grub
2. Checked which menu entries I had:
grep menuentry /boot/grub/grub.cfg
3. Constructed the default entry:
grub-set-default "Erweiterte Optionen für Debian GNU/Linux>Debian
GNU/Linux, with Linux 3.16.0-4-amd64 (recovery mode)"
Note how I explicitly specified the kernel as a subcomponent of the
advanced menu.
(sorry for the Geman locale)