Missing `linux-update-symlinks` causes Linux package installation to fail

Status changed to 'Confirmed' because the bug affects multiple users.

This should fix it:

https://bugs.launchpad.net/ubuntu/+source/linux-base/+bug/1766728

Same problem with Kernel 4.14.36: http://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.36/

Also I would suspect (but cannot confirm) that Kernel 4.16.4 will suffer the same fate.

For the first time all three of these kernels (including OP's 4.17-rc2) deviated from history where there were three `.deb` files: headers-all, headers, linux-image (aka image_unsigned). A fourth `.deb` was introduced called: ` linux-modules-4.14.36-041436-generic_4.14.36-041436.201804240906_amd64.deb`

I am still having this issue with a fresh install of 16.04. Can anyone give an update to this bug

Same as Jason Pereira, I've this issue with fresh 16.04 intall, from network.

I'm also seeing this, when attempting to provision a vagrant box with 16.04. I have, in my Vagrantfile:

```
config.vm.box_url = 'https://app.vagrantup.com/bento/boxes/ubuntu-16.04/versions/2.3.1/providers/virtualbox.box'
```

And I see the error during `vagrant up --provision`:

```
...
Setting up linux-image-4.4.0-143-generic (4.4.0-143.169) ...
/var/lib/dpkg/info/linux-image-4.4.0-143-generic.postinst: 50: /var/lib/dpkg/info/linux-image-4.4.0-143-generic.postinst: linux-update-symlinks: not found
dpkg: error processing package linux-image-4.4.0-143-generic (--configure):
    subprocess installed post-installation script returned error exit status 127
...
```

Related to #1820755 - although the new linux-base is now available in xenial-updates, the kernel packages do not version their depends to demand the new version, so apt-get will not necessarily install it (which causes base-installer to fail, since debootstrap will not have upgraded from xenial-updates prior to installing base-installer/kernel/image, and will not upgrade when the linux-image-generic Depends are already satisfied)