Why doesn't apt-get autoremove remove my old kernels?

As to answer why , refer to the file /etc/apt/apt.conf.d/01autoremove-kernels

As you can see, apt is told to never autoremove the kernels , as told by another (script) file, /etc/kernel/postinst.d/apt-auto-removal. And here it is:

If you manually install 2 chosen kernels, ie the first and the current one, then apt-autoremove will only ever remove the older versions you didn't manually install, so you will always have those 2 options plus whatever the latest one is.

Update:

In the /etc/kernel/postinst.d/apt-auto-removal there is this part:

if [ "$latest_version" != "$installed_version" ] \
   || [ "$latest_version" != "$running_version" ] \
   || [ "$installed_version" != "$running_version" ]
then
        # We have at least two kernels that we have reason to think the
        # user wants, so don't save the second-newest version.
        previous_version=
fi

So if you compare the output of 01autoremove-kernels file and uname -r you'll realize that the currently running kernel and the most recent before it, are kept to be never removed by that script. There turns out is another file /etc/apt/apt.conf.d/01autoremove, where there is lines:

    APT
    {
      NeverAutoRemove
      {
            "^firmware-linux.*";
            "^linux-firmware$";
      };
  VersionedKernelPackages
  {
        # linux kernels
        "linux-image";
        "linux-headers";
        "linux-image-extra";
        "linux-signed-image";
        # kfreebsd kernels
        "kfreebsd-image";
        "kfreebsd-headers";
        # hurd kernels
        "gnumach-image";
        # (out-of-tree) modules
        ".*-modules";
        ".*-kernel";
        "linux-backports-modules-.*";
        # tools
        "linux-tools";
  };

So you could comment these out, and it will allow you to auto-remove the kernels with apt-autoremove, though remember - do this at your own risk

For me it helped to install latest (X)ubuntu (15.10). In earlier releases kernel packages may be marked as manually installed, at least, if installed by using Software Updater, so that sudo apt-get autoremove --purge can't delete them. There are bug reports concerning the issue: Bug #1175637, Bug #1439769

In earlier release, you could try to mark kernel packages automatically installed by sudo apt-mark auto $(apt-mark showmanual | grep -E "^linux-([[:alpha:]]+-)+[[:digit:].]+-[^-]+(|-.+)$") and run sudo apt-get autoremove --purge thereafter to see, if it makes difference. The command should still not remove kernels packages shown in /etc/apt/apt.conf.d/01autoremove-kernels, but it is safest to run apt-get autoremove with --dry-run option first.

Alternatively, you could use linux-purge to purge old kernels even more selectively or even if they were manually installed.