/etc/grub.d/00_header contains the following:

grub_lang=`echo $LANG | cut -d . -f 1`

[...]

if [ "x${LANG}" != "xC" ] &&  [ "x${LANG}" != "x" ]; then
  cat << EOF
  set locale_dir=\$prefix/locale
  set lang=${grub_lang}
  insmod gettext
EOF
fi

This means that the grub.cfg file that will be generated depends on
the locales used at generation time, i.e. the locales of the user
who does the upgrade. This makes no sense.

I noticed this problem on another machine[*] because after a kernel
upgrade, the grub.cfg file was regenerated, and at this time, I have
LANG=POSIX as a user. So, 3 lines got added to this file:

  set locale_dir=$prefix/locale
  set lang=POSIX
  insmod gettext

If grub.cfg needs to depend on the locales, this should be against
the default locales, i.e. I think that LANG should be unset, then
/etc/default/locale should be sourced (LANG may be set there).

However the default locales can change at any time, and the grub.cfg
file will generally not be regenerated after that. So, I would say
that this is still not a good solution.

[*] I can't report the bug from it yet because I don't have a MUA
there; it's still being installed. Anyway the problem is not specific
to this machine.