I was having the same problem on Debian 9, but my PC was old.
When I looked at linux-image and linux-header in synaptic, there were installations for old PCs and modern PCs, on my old PC was installed the version for modern Pcs. I installed the correct version and uninstalled the wrong one. Worked perfectly.
Ex:
linux-image-4.9.0.4-686 - Linux 4.9 for older PCs
linux-image-686 - Linux for older PCs (meta-package)
linux-image-4.9.0.4-686-pae - Linux 4.9 for modern PCs
linux-image-686-pae - Linux for modern PCs (meta-package)
I was having the same problem on Debian 9, but my PC was old.
When I looked at linux-image and linux-header in synaptic, there were installations for old PCs and modern PCs, on my old PC was installed the version for modern Pcs. I installed the correct version and uninstalled the wrong one. Worked perfectly.
Ex: 4.9.0.4- 686 - Linux 4.9 for older PCs
linux-image-
linux-image-686 - Linux for older PCs (meta-package)
linux-image- 4.9.0.4- 686-pae - Linux 4.9 for modern PCs
linux-image-686-pae - Linux for modern PCs (meta-package)