Ubuntu 16.04 - kernel packages have been kept back
If the upgrade of an existing package would require a "new" package (e.g. not-yet-installed) to be installed, then that particular existing package will be "kept back."
According to the man apt-get, upgrade by default does not install other not-yet-installed packages:
upgrade
... under no circumstances are currently installed packages removed, or packages not already installed retrieved and installed.
--with-new-pkgs
Allow installing new packages when used in conjunction with upgrade. This is useful if the update of a installed package requires new dependencies to be installed. Instead of holding the package back upgrade will upgrade the package and install the new dependencies. ...
so, --with-new-pkgs needs to be added to allow inclusion of the related other packages.
sudo apt-get --with-new-pkgs upgrade
--with-new-pkgs allows the related "not-yet-installed" packages to be installed with a Y/n interactive prompt.
Also, as an added benefit, sudo apt-get --with-new-pkgs upgrade does NOT have side affect of causing packages to be marked as manually installed.
Update
Ubuntu 18.04 provides a newer, streamlined syntax of apt which can be used instead of apt-get.
sudo apt upgrade --with-new-pkgs
Although the general topic "packages have been kept back" has been answered here before : There is something strange going on today ... when I executed sudo apt update a few hours ago, the new kernel 4.8.0-42 was offered for installation. I executed sudo apt dist-upgrade and after the restart of the system (Ubuntu 16.10 workstation), I was running that new kernel.
A few hours later I wanted to upgrade my Ubuntu server installation, but a new kernel was not offered. To re-check the situation I restored my clonezilla system backup image from yesterday on the Ubuntu workstation to re-check the situation. This time the new kernel was not offered anymore. It seems that kernel 4.8.0-42 was accidentally pushed to the main repository and is on the way to getting pushed back to the proposed repository - maybe Canonical has found a bug.
You have opted in to the HWE stack of Ubuntu 16.04, which means that you are using the kernel 4.8 of Ubuntu 16.10. Hence everything happens with the kernel in Ubuntu 16.10 first, a possible explanation for the time delay of the refreshing process for the Ubuntu 16.04 LTS repositories.
When you run sudo apt update a little bit later again, the message you got should not appear anymore. Conclusion : Do not run sudo apt dist-upgrade and wait right until the repositories got updated and the message about the held back kernel packages does not appear any longer. By the way, exactly the same happened with the kernel version 4.8.0-40 already some time ago.
Being a relatively new Ubuntu user I bumped into the same issue and apparently solved it. I found that there were three pending updates on Ubuntu Software with the same names as the ones listed on the terminal as listed below:
The following packages have been kept back:
linux-generic-hwe-16.04 linux-headers-generic-hwe-16.04 linux-image-generic-hwe-16.04
0 upgraded, 0 newly installed, 0 to remove and 3 not upgraded.
After installing those updates from Ubuntu Software I went back to the Terminal and did sudo apt-get update and sudo apt-get upgrade. The result:
The following packages were automatically installed and are no longer required:
linux-headers-4.8.0-41 linux-headers-4.8.0-41-generic linux-headers-4.8.0-44 linux-headers-4.8.0-44-generic linux-image-4.8.0-41-generic
linux-image-4.8.0-44-generic linux-image-extra-4.8.0-41-generic linux-image-extra-4.8.0-44-generic
Use 'sudo apt autoremove' to remove them.
0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
Not being an expert I think installing updates from the Ubuntu Software seems to solve the problem. And the problem seems to be that there is no full communication between Ubuntu software and the apt-get update and upgrade packages. I'm sure you'll find a better explanation but I wanted to share this with you.