Having trouble upgrading Linux kernel in Xenial

Question

I have downloaded the latest kernel and headers but Ubuntu is not using it on reboot. Only 3.19.0-22 is working, when I choose one in the Grub menu.

Can I somehow refresh that list or force Ubuntu to choose the new Kernel (linux-image-4.6.2-040602-generic)

Here is a list of installed images and headers:

$ dpkg -l | grep linux-headers
ii  linux-headers-3.19.8-992                             3.19.8-992.201605312242                             all          Header files related to Linux kernel version 3.19.8
ii  linux-headers-3.19.8-992-generic                     3.19.8-992.201605312242                             amd64        Linux kernel headers for version 3.19.8 on 64 bit x86 SMP
ii  linux-headers-4.6.2-040602                           4.6.2-040602.201606100516                           all          Header files related to Linux kernel version 4.6.2
ii  linux-headers-4.6.2-040602-generic                   4.6.2-040602.201606100516                           amd64        Linux kernel headers for version 4.6.2 on 64 bit x86 SMP

$ dpkg -l | grep linux-image
rc  linux-image-3.19.0-18-generic                        3.19.0-18.18                                        amd64        Linux kernel image for version 3.19.0 on 64 bit x86 SMP
rc  linux-image-3.19.0-21-generic                        3.19.0-21.21                                        amd64        Linux kernel image for version 3.19.0 on 64 bit x86 SMP
ii  linux-image-3.19.0-22-generic                        3.19.0-22.22                                        amd64        Linux kernel image for version 3.19.0 on 64 bit x86 SMP
ii  linux-image-4.6.2-040602-generic                     4.6.2-040602.201606100516                           amd64        Linux kernel image for version 4.6.2 on 64 bit x86 SMP
rc  linux-image-extra-3.19.0-18-generic                  3.19.0-18.18                                        amd64        Linux kernel extra modules for version 3.19.0 on 64 bit x86 SMP
rc  linux-image-extra-3.19.0-21-generic                  3.19.0-21.21                                        amd64        Linux kernel extra modules for version 3.19.0 on 64 bit x86 SMP
ii  linux-image-extra-3.19.0-22-generic                  3.19.0-22.22                                        amd64        Linux kernel extra modules for version 3.19.0 on 64 bit x86 SMP

$ uname -r
3.19.0-22-generic

I hope someone can help me

// Ulrik McArdle

UPDATE:

Output of sudo update-grub:

Searching for GRUB installation directory ... found: /boot/grub
Searching for default file ... found: /boot/grub/default
Testing for an existing GRUB menu.lst file ... found: /boot/grub/menu.lst
Searching for splash image ... none found, skipping ...
Found kernel: /boot/vmlinuz-4.6.2-040602-generic
Found kernel: /boot/vmlinuz-3.19.0-22-generic
Found kernel: /boot/memtest86+.bin
Found kernel: /boot/vmlinuz-4.6.2-040602-generic
Found kernel: /boot/vmlinuz-3.19.0-22-generic
Found kernel: /boot/memtest86+.bin
Updating /boot/grub/menu.lst ... done

UPDATE 2:

Here an image of my Grub when I'm booting up: My Grub when booting

FINAL SOLUTION:

I reinstalled the Grub bootloader:

# purge old and reinstall new to sda
sudo apt-get purge grub grub-pc grub-common
sudo mv /boot/grub /boot/grub_backup
sudo mkdir /boot/grub
sudo apt-get install grub-pc grub-common
sudo grub-install --recheck /dev/sda
sudo update-grub

Answer 1

Okay as mentioned in my post the final answer was to reinstall Grub:

# purge old and reinstall new to sda
sudo apt-get purge grub grub-pc grub-common
sudo mv /boot/grub /boot/grub_backup
sudo mkdir /boot/grub
sudo apt-get install grub-pc grub-common
sudo grub-install --recheck /dev/sda
sudo update-grub

Answer 2

You need to reload grub. Usually, this problem happens automatically when you install a new kernel, so how did you install the kernel? To update grub, use this command.

sudo update-grub

And then restart your computer.