I've been seeing this for some time -- probably since July, but I'm not sure.  (Just back from a month or so offline, so my memory is fading.)

Thanks to @tommy-trussell for narrowing it down to /var/lib/apt/extended_states.  I believe I've narrowed it further; on my system, deleting a few specific entries from that file is enough to make update-manager display the updates again.  But *which* specific entries is ... interesting.

Summary
=======

These are the entries that need to be removed:
    linux-signed-image-4.13.0-43-generic
    linux-image-extra-4.13.0-43-generic
    linux-signed-image-4.13.0-45-generic
    linux-image-extra-4.13.0-45-generic
    linux-modules-extra-4.15.0-24-generic

But note that installing the pending kernel updates caused a non-obvious addition to this list.


Details
=======


My system is:
    $ cat /etc/lsb-release
    DISTRIB_ID=Ubuntu
    DISTRIB_RELEASE=16.04
    DISTRIB_CODENAME=xenial
    DISTRIB_DESCRIPTION="Ubuntu 16.04.5 LTS"

    In case it matters:
      - It's an EFI system
      - Xenial was a clean install, not an upgrade over an earlier version


At the start of my investigation:
    $ uname -a
    Linux shekere 4.15.0-29-generic #31~16.04.1-Ubuntu SMP Wed Jul 18 08:54:04 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux

    The installed packages that appear to be relevant were:
        linux-image-extra-4.13.0-43-generic
        linux-image-extra-4.13.0-45-generic
        linux-modules-extra-4.15.0-24-generic
        linux-modules-extra-4.15.0-29-generic
        linux-signed-image-4.13.0-43-generic
        linux-signed-image-4.13.0-45-generic
    (There were also corresponding versions of linux-image and linux-headers, but those don't seem to matter re. this bug).

    Deleting *all* of the following four entries from extended_states made update-manager work properly:

	Package: linux-signed-image-4.13.0-43-generic
	Architecture: amd64
	Auto-Installed: 1

	Package: linux-image-extra-4.13.0-43-generic
	Architecture: amd64
	Auto-Installed: 1

	Package: linux-signed-image-4.13.0-45-generic
	Architecture: amd64
	Auto-Installed: 1

	Package: linux-image-extra-4.13.0-45-generic
	Architecture: amd64
	Auto-Installed: 1


I then installed the pending kernel-related updates:
    Of the many updates waiting to be installed were these:

        linux-headers-4.15.0-33
        linux-headers-4.15.0-33-generic
        linux-image-4.15.0-33-generic
        linux-modules-4.15.0-33-generic
        linux-modules-extra-4.15.0-33-generic

    I:
        1. reverted to the status-quo-ante version of extended_status (which of course caused update-manager to misbehave again)
        2. manually installed those five packages
        3. tested
        4. rebooted into the new kernel
        5. tested again
    
    As expected, the reboot made no difference; same results at steps (3) and (5).

    Here's how things stand now:

	$ uname -a
	Linux shekere 4.15.0-33-generic #36~16.04.1-Ubuntu SMP Wed Aug 15 17:21:05 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux

	extended_states did *not* acquire any new entries for the -4.15.0.33 packages.  (Perhaps this is because I "apt install"ed them, instead of letting dist-upgrade do it?)
    
	To make update-manager work, I now have to remove those same four extended_states entries, PLUS ONE MORE:

	    Package: linux-modules-extra-4.15.0-24-generic
	    Architecture: amd64
	    Auto-Installed: 1


I had intended to test again after installing the rest of the pending updates, but alas, update-manager just gives me a no-pending-updates dialog box.  I doubt that this second round of updates will have made any difference; but if that needs to be tested, it'll have to wait until another package update becomes available....