bug #1472351 seems to be the cause for this issue. I guess you have some ZFS package installed that has a Recommends tag for linux-headers or linux-image, too.
-- You received this bug notification because you are a member of Ubuntu Touch seeded packages, which is subscribed to apt in Ubuntu. https://bugs.launchpad.net/bugs/1605160 Title: kernel autoremove not working Status in apt package in Ubuntu: Confirmed Bug description: On one 16.04 machine I have 5 4.4.0-kernels in /boot now (on another machine even 6): -rw------- 1 root root 7013968 Apr 19 00:21 vmlinuz-4.4.0-21-generic -rw------- 1 root root 7015440 Mai 13 01:55 vmlinuz-4.4.0-22-generic -rw------- 1 root root 7020176 Jun 8 23:39 vmlinuz-4.4.0-24-generic -rw------- 1 root root 7026864 Jun 24 14:03 vmlinuz-4.4.0-28-generic -rw------- 1 root root 7047504 Jul 13 03:59 vmlinuz-4.4.0-31-generic Should not hapen that way. apt-get autoremove should clean that, but doesn't. regards ProblemType: Bug DistroRelease: Ubuntu 16.04 Package: apt 1.2.12~ubuntu16.04.1 ProcVersionSignature: Ubuntu 4.4.0-31.50-generic 4.4.13 Uname: Linux 4.4.0-31-generic x86_64 NonfreeKernelModules: zfs zunicode zcommon znvpair zavl ApportVersion: 2.20.1-0ubuntu2.1 Architecture: amd64 CurrentDesktop: XFCE Date: Thu Jul 21 11:41:43 2016 InstallationDate: Installed on 2016-04-22 (89 days ago) InstallationMedia: Lubuntu 16.04 LTS "Xenial Xerus" - Release amd64 (20160420) SourcePackage: apt UpgradeStatus: No upgrade log present (probably fresh install) To manage notifications about this bug go to: https://bugs.launchpad.net/ubuntu/+source/apt/+bug/1605160/+subscriptions -- Mailing list: https://launchpad.net/~touch-packages Post to : touch-packages@lists.launchpad.net Unsubscribe : https://launchpad.net/~touch-packages More help : https://help.launchpad.net/ListHelp