Linux-Headers Reinstall

First try the fix-missing feature

sudo apt upgrade --fix-missing

Second, try to install headers from the command line:

Maybe you just need these specific headers (linux-headers-4.4.0-98-generic):

sudo apt install linux-headers-4.4.0-98-generic

If that doesn't work, see what kernel type you are using (generic, lowlatency, etc.):

uname -r

This will return something like "4.15.0-30-generic" or "4.15.0-30-lowlatency". Install/Reinstall the headers that correspond to your kernel type. Eg if it is the generic kernel (most likely):

sudo apt install --reinstall linux-headers-generic

This will cause the current headers for your current kernel to be automatically installed and upgraded.

If above doesn't work, try the following:

Update to latest kernel:

sudo apt update && sudo apt upgrade

Reboot to ensure you are using latest kernel.

Purge out old headers and removed unused apps/kernels:

sudo apt remove --purge linux-headers-*
sudo apt autoremove && sudo apt autoclean

Reinstall the headers:

sudo apt install linux-headers-generic

These commands worked for me.

Find linux-headers-4.4.0-98

$ apt-cache search linux-headers-4.4.0-98
linux-headers-4.4.0-98 - Header files related to Linux kernel version 4.4.0
linux-headers-4.4.0-98-generic - Linux kernel headers for version 4.4.0 on 64 bit x86 SMP
linux-headers-4.4.0-98-lowlatency - Linux kernel headers for version 4.4.0 on 64 bit x86 SMP

Install linux-headers-4.4.0-98

For your reinstall you will type:

sudo apt install --reinstall linux-headers-4.4.0-98-generic

But for myself it's a new package so I'll use:

$ sudo apt install linux-headers-4.4.0-98-generic
Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following additional packages will be installed:
  linux-headers-4.4.0-98
The following NEW packages will be installed:
  linux-headers-4.4.0-98 linux-headers-4.4.0-98-generic
0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
Need to get 10.7 MB of archives.
After this operation, 78.2 MB of additional disk space will be used.
Do you want to continue? [Y/n] y
Get:1 http://ca.archive.ubuntu.com/ubuntu xenial-updates/main amd64 linux-headers-4.4.0-98 all 4.4.0-98.121 [9,913 kB]
Get:2 http://ca.archive.ubuntu.com/ubuntu xenial-updates/main amd64 linux-headers-4.4.0-98-generic amd64 4.4.0-98.121 [793 kB]
Fetched 10.7 MB in 3s (3,463 kB/s)                  
Selecting previously unselected package linux-headers-4.4.0-98.
(Reading database ... 288111 files and directories currently installed.)
Preparing to unpack .../linux-headers-4.4.0-98_4.4.0-98.121_all.deb ...
Unpacking linux-headers-4.4.0-98 (4.4.0-98.121) ...
Selecting previously unselected package linux-headers-4.4.0-98-generic.
Preparing to unpack .../linux-headers-4.4.0-98-generic_4.4.0-98.121_amd64.deb ...
Unpacking linux-headers-4.4.0-98-generic (4.4.0-98.121) ...
Setting up linux-headers-4.4.0-98 (4.4.0-98.121) ...
Setting up linux-headers-4.4.0-98-generic (4.4.0-98.121) ...
Examining /etc/kernel/header_postinst.d.
run-parts: executing /etc/kernel/header_postinst.d/dkms 4.4.0-98-generic /boot/vmlinuz-4.4.0-98-generic

Remove linux-headers-4.4.0-98

Because this was a test and I don't need them on my machine:

$ sudo apt remove --purge linux-headers-4.4.0-98-generic
Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following package was automatically installed and is no longer required:
  linux-headers-4.4.0-98
Use 'sudo apt autoremove' to remove it.
The following packages will be REMOVED:
  linux-headers-4.4.0-98-generic*
0 upgraded, 0 newly installed, 1 to remove and 0 not upgraded.
After this operation, 7,431 kB disk space will be freed.
Do you want to continue? [Y/n] y
(Reading database ... 314874 files and directories currently installed.)
Removing linux-headers-4.4.0-98-generic (4.4.0-98.121) ...
dpkg: warning: while removing linux-headers-4.4.0-98-generic, directory '/lib/modules/4.4.0-98-generic' not empty so not removed

Cleanup leftover garbage

I see there is left over garbage in the last line so I'll manually clean it up:

$ sudo rm -rf /lib/modules/4.4.0-98-generic
$ ll /lib/modules/4.4.0-98-generic
ls: cannot access '/lib/modules/4.4.0-98-generic': No such file or directory

Now 4.4.0-98 is almost removed. It is completely removed with:

sudo apt autoremove

If you have internet connection...

Run software-properties-gtk. In Ubuntu Software tab, notice the Download from field. What do you have there? (I use "ubuntu.trumpetti.atm.tut.fi/ubuntu" as I live in Finland; at least that server has linux-headers-4.4.0-98 currently.) Try to change the setting in the field. In Updates tab see that you have "Important security updates" checked. Do what the dialog asks. And close it. Then do the following in terminal (but stop, if there are errors and please report them in comments.):

sudo apt install --reinstall linux-headers-4.4.0-98
sudo apt-mark auto linux-headers-4.4.0-98
sudo apt install linux-generic

and run update-manager to install further updates.

If you do not have internet connnection...

If the problem is that you do not have internet connection, but you have Ubuntu CD-ROM/DVD installation media, you can use it as a software source, see here. If you do not have optical media, but USB one, trye this.

Check if the media contains some other kernel:

apt-cache policy linux-generic

If it contains different version, you had better purge the 4.4.0-98 headers:

sudo dpkg --purge --force-remove-reinstreq linux-headers-4.4.0-98 linux-headers-4.4.0-98-generic

And install the kernel from the media:

sudo apt install linux-generic

And finally purge the old kernel images:

sudo apt purge linux-image-4.4.0-98-generic

After trying many of the options above, (perhaps it helped) I tried the following command and it worked:

sudo apt --fix-broken install

I hope it works of others...