Not rebooting to the lastest kernel after update to grub 2

I'm used to installing ubuntu core updates from apt, and then rebooting to get to the latest kernel. However, this process doesn't seem to be working right on one of my servers. Kernel 4.10.0-21 is installed but the machine only seems to use 4.10.0-20 when it reboots.

During the apt update process to grub2, a dialog asked me if I want to chain my legacy grub configuration. I chose "no". I think that may be part of the problem.

Updating grub seems to do the right thing, it puts the newest kernel first:

$ sudo update-grub
Generating grub configuration file ...
Found linux image: /boot/vmlinuz-4.10.0-21-generic
Found initrd image: /boot/initrd.img-4.10.0-21-generic
Found linux image: /boot/vmlinuz-4.10.0-20-generic
Found initrd image: /boot/initrd.img-4.10.0-20-generic
Found memtest86+ image: /boot/memtest86+.elf
Found memtest86+ image: /boot/memtest86+.bin
done

My /etc/grub/default file says that kernel 0 should be the default:

GRUB_DEFAULT=0
GRUB_HIDDEN_TIMEOUT_QUIET=true
GRUB_TIMEOUT=3
GRUB_DISTRIBUTOR=`lsb_release -i -s 2> /dev/null || echo Debian`
GRUB_CMDLINE_LINUX_DEFAULT="quiet splash"
GRUB_CMDLINE_LINUX=""

I can verify that grub.cfg gets the kernels added:

$ grep menuentry /boot/grub/grub.cfg
...
    menuentry 'Ubuntu, with Linux 4.10.0-21-generic' --class ubuntu --class gnu-linux --class gnu --class os $menuentry_id_option 'gnulinux-4.10.0-21-generic-advanced-6af3f559-58c5-4c56-b1c8-ffe02c700c97' {
    menuentry 'Ubuntu, with Linux 4.10.0-21-generic (recovery mode)' --class ubuntu --class gnu-linux --class gnu --class os $menuentry_id_option 'gnulinux-4.10.0-21-generic-recovery-6af3f559-58c5-4c56-b1c8-ffe02c700c97' {
    menuentry 'Ubuntu, with Linux 4.10.0-20-generic' --class ubuntu --class gnu-linux --class gnu --class os $menuentry_id_option 'gnulinux-4.10.0-20-generic-advanced-6af3f559-58c5-4c56-b1c8-ffe02c700c97' {
    menuentry 'Ubuntu, with Linux 4.10.0-20-generic (recovery mode)' --class ubuntu --class gnu-linux --class gnu --class os $menuentry_id_option 'gnulinux-4.10.0-20-generic-recovery-6af3f559-58c5-4c56-b1c8-ffe02c700c97' {
...

$ grep -Poz "menuentry 'Ubuntu' (.|\n)*?\}" /boot/grub/grub.cfg
menuentry 'Ubuntu' --class ubuntu --class gnu-linux --class gnu --class os $menuentry_id_option 'gnulinux-simple-6af3f559-58c5-4c56-b1c8-ffe02c700c97' {
    recordfail
    load_video
    gfxmode $linux_gfx_mode
    insmod gzio
    if [ x$grub_platform = xxen ]; then insmod xzio; insmod lzopio; fi
    insmod part_msdos
    insmod ext2
    set root='hd0,msdos1'
    if [ x$feature_platform_search_hint = xy ]; then
      search --no-floppy --fs-uuid --set=root --hint-bios=hd0,msdos1 --hint-efi=hd0,msdos1 --hint-baremetal=ahci0,msdos1 --hint='hd0,msdos1'  6af3f559-58c5-4c56-b1c8-ffe02c700c97
    else
      search --no-floppy --fs-uuid --set=root 6af3f559-58c5-4c56-b1c8-ffe02c700c97
    fi
        linux   /boot/vmlinuz-4.10.0-21-generic root=UUID=6af3f559-58c5-4c56-b1c8-ffe02c700c97 ro  quiet splash $vt_handoff
    initrd  /boot/initrd.img-4.10.0-21-generic
}

The kernel file actually exists on disk:

$ ls -l /boot/vmlinuz-4.10.0-21-generic
-rw------- 1 root root 7575312 Apr 28 06:41 /boot/vmlinuz-4.10.0-21-generic

On the chance that it was corrupted somehow, I tried re-installing it:

$ sudo apt-get install --reinstall linux-image-4.10.0-21-generic

dpkg shows that both kernels are installed:

$ dpkg -l | grep ii | grep linux-image-[0-9].*-generic
ii  linux-image-4.10.0-20-generic               4.10.0-20.22                              amd64        Linux kernel image for version 4.10.0 on 64 bit x86 SMP
ii  linux-image-4.10.0-21-generic               4.10.0-21.23                              amd64        Linux kernel image for version 4.10.0 on 64 bit x86 SMP

However after rebooting:

$ uname -r
4.10.0-20-generic

$ cat /proc/version 
Linux version 4.10.0-20-generic (buildd@lcy01-05) (gcc version 6.3.0 20170406 (Ubuntu 6.3.0-12ubuntu2) ) #22-Ubuntu SMP Thu Apr 20 09:22:42 UTC 2017

$ cat /proc/cmdline
root=UUID=6af3f559-58c5-4c56-b1c8-ffe02c700c97 ro quiet splash 

I really think that grub legacy is somehow still being used on this machine. /boot/grub/menu.1st has references to 20 but not to 21:

title           Ubuntu 17.04, kernel 4.10.0-20-generic
root            (hd0,0)
kernel          /boot/vmlinuz-4.10.0-20-generic root=UUID=6af3f559-58c5-4c56-b1c8-ffe02c700c97 ro quiet splash
initrd          /boot/initrd.img-4.10.0-20-generic
quiet

title           Ubuntu 17.04, kernel 4.10.0-20-generic (recovery mode)
root            (hd0,0)
kernel          /boot/vmlinuz-4.10.0-20-generic root=UUID=6af3f559-58c5-4c56-b1c8-ffe02c700c97 ro  single
initrd          /boot/initrd.img-4.10.0-20-generic

title           Ubuntu 17.04, kernel 4.8.0-49-generic
root            (hd0,0)
kernel          /boot/vmlinuz-4.8.0-49-generic root=UUID=6af3f559-58c5-4c56-b1c8-ffe02c700c97 ro quiet splash
initrd          /boot/initrd.img-4.8.0-49-generic
quiet

title           Ubuntu 17.04, kernel 4.8.0-49-generic (recovery mode)
root            (hd0,0)
kernel          /boot/vmlinuz-4.8.0-49-generic root=UUID=6af3f559-58c5-4c56-b1c8-ffe02c700c97 ro  single
initrd          /boot/initrd.img-4.8.0-49-generic

title           Ubuntu 17.04, memtest86+
root            (hd0,0)
kernel          /boot/memtest86+.bin
quiet

This machine is in a data center, and I don't have console access during the reboot process. I'm unable to see what grub says during the reboot, I can only ssh in after it is up and running.

What could be causing the newest kernel not to be used and how can I fix it?