I removed many of linux-images of 3.13.0-x versions, I left few versions installed.
~ > dpkg --list | grep linux-image
rc linux-image-3.13.0-83-generic 3.13.0-83.127 amd64 Linux kernel image for version 3.13.0 on 64 bit x86 SMP
ii linux-image-3.13.0-85-generic 3.13.0-85.129 amd64 Linux kernel image for version 3.13.0 on 64 bit x86 SMP
ii linux-image-3.13.0-86-generic 3.13.0-86.131 amd64 Linux kernel image for version 3.13.0 on 64 bit x86 SMP
rc linux-image-extra-3.13.0-83-generic 3.13.0-83.127 amd64 Linux kernel extra modules for version 3.13.0 on 64 bit x86 SMP
ii linux-image-extra-3.13.0-85-generic 3.13.0-85.129 amd64 Linux kernel extra modules for version 3.13.0 on 64 bit x86 SMP
ii linux-image-extra-3.13.0-86-generic 3.13.0-86.131 amd64 Linux kernel extra modules for version 3.13.0 on 64 bit x86 SMP
ii linux-image-generic 3.13.0.86.92 amd64 Generic Linux kernel image
ii linux-image-generic-lts-raring 3.13.0.86.92 amd64 Generic Linux kernel image
As you can see there are only 3.13.0-x versions.
But also I have a lot of linux-headers for 3.16.0-x and 3.19.0-x versions.
ii linux-headers-3.13.0-85 3.13.0-85.129 all Header files related to Linux kernel version 3.13.0
ii linux-headers-3.13.0-85-generic 3.13.0-85.129 amd64 Linux kernel headers for version 3.13.0 on 64 bit x86 SMP
ii linux-headers-3.13.0-86 3.13.0-86.131 all Header files related to Linux kernel version 3.13.0
ii linux-headers-3.13.0-86-generic 3.13.0-86.131 amd64 Linux kernel headers for version 3.13.0 on 64 bit x86 SMP
ii linux-headers-3.16.0-43 3.16.0-43.58~14.04.1 all Header files related to Linux kernel version 3.16.0
ii linux-headers-3.16.0-43-generic 3.16.0-43.58~14.04.1 amd64 Linux kernel headers for version 3.16.0 on 64 bit x86 SMP
ii linux-headers-3.16.0-44 3.16.0-44.59~14.04.1 all Header files related to Linux kernel version 3.16.0
ii linux-headers-3.16.0-44-generic 3.16.0-44.59~14.04.1 amd64 Linux kernel headers for version 3.16.0 on 64 bit x86 SMP
ii linux-headers-3.16.0-45 3.16.0-45.60~14.04.1 all Header files related to Linux kernel version 3.16.0
ii linux-headers-3.16.0-45-generic 3.16.0-45.60~14.04.1 amd64 Linux kernel headers for version 3.16.0 on 64 bit x86 SMP
ii linux-headers-3.16.0-46 3.16.0-46.62~14.04.1 all Header files related to Linux kernel version 3.16.0
ii linux-headers-3.16.0-46-generic 3.16.0-46.62~14.04.1 amd64 Linux kernel headers for version 3.16.0 on 64 bit x86 SMP
ii linux-headers-3.16.0-48 3.16.0-48.64~14.04.1 all Header files related to Linux kernel version 3.16.0
ii linux-headers-3.16.0-48-generic 3.16.0-48.64~14.04.1 amd64 Linux kernel headers for version 3.16.0 on 64 bit x86 SMP
ii linux-headers-3.16.0-49 3.16.0-49.65~14.04.1 all Header files related to Linux kernel version 3.16.0
ii linux-headers-3.16.0-49-generic 3.16.0-49.65~14.04.1 amd64 Linux kernel headers for version 3.16.0 on 64 bit x86 SMP
ii linux-headers-3.16.0-50 3.16.0-50.67~14.04.1 all Header files related to Linux kernel version 3.16.0
ii linux-headers-3.16.0-50-generic 3.16.0-50.67~14.04.1 amd64 Linux kernel headers for version 3.16.0 on 64 bit x86 SMP
ii linux-headers-3.16.0-51 3.16.0-51.69~14.04.1 all Header files related to Linux kernel version 3.16.0
ii linux-headers-3.16.0-51-generic 3.16.0-51.69~14.04.1 amd64 Linux kernel headers for version 3.16.0 on 64 bit x86 SMP
ii linux-headers-3.16.0-52 3.16.0-52.71~14.04.1 all Header files related to Linux kernel version 3.16.0
ii linux-headers-3.16.0-52-generic 3.16.0-52.71~14.04.1 amd64 Linux kernel headers for version 3.16.0 on 64 bit x86 SMP
ii linux-headers-3.16.0-53 3.16.0-53.72~14.04.1 all Header files related to Linux kernel version 3.16.0
ii linux-headers-3.16.0-53-generic 3.16.0-53.72~14.04.1 amd64 Linux kernel headers for version 3.16.0 on 64 bit x86 SMP
ii linux-headers-3.16.0-55 3.16.0-55.74~14.04.1 all Header files related to Linux kernel version 3.16.0
ii linux-headers-3.16.0-55-generic 3.16.0-55.74~14.04.1 amd64 Linux kernel headers for version 3.16.0 on 64 bit x86 SMP
ii linux-headers-3.16.0-56 3.16.0-56.75~14.04.1 all Header files related to Linux kernel version 3.16.0
ii linux-headers-3.16.0-56-generic 3.16.0-56.75~14.04.1 amd64 Linux kernel headers for version 3.16.0 on 64 bit x86 SMP
ii linux-headers-3.16.0-57 3.16.0-57.77~14.04.1 all Header files related to Linux kernel version 3.16.0
ii linux-headers-3.16.0-57-generic 3.16.0-57.77~14.04.1 amd64 Linux kernel headers for version 3.16.0 on 64 bit x86 SMP
ii linux-headers-3.16.0-59 3.16.0-59.79~14.04.1 all Header files related to Linux kernel version 3.16.0
ii linux-headers-3.16.0-59-generic 3.16.0-59.79~14.04.1 amd64 Linux kernel headers for version 3.16.0 on 64 bit x86 SMP
ii linux-headers-3.16.0-60 3.16.0-60.80~14.04.1 all Header files related to Linux kernel version 3.16.0
ii linux-headers-3.16.0-60-generic 3.16.0-60.80~14.04.1 amd64 Linux kernel headers for version 3.16.0 on 64 bit x86 SMP
ii linux-headers-3.16.0-62 3.16.0-62.83~14.04.1 all Header files related to Linux kernel version 3.16.0
ii linux-headers-3.16.0-62-generic 3.16.0-62.83~14.04.1 amd64 Linux kernel headers for version 3.16.0 on 64 bit x86 SMP
ii linux-headers-3.16.0-67 3.16.0-67.87~14.04.1 all Header files related to Linux kernel version 3.16.0
ii linux-headers-3.16.0-67-generic 3.16.0-67.87~14.04.1 amd64 Linux kernel headers for version 3.16.0 on 64 bit x86 SMP
ii linux-headers-3.16.0-70 3.16.0-70.90~14.04.1 all Header files related to Linux kernel version 3.16.0
ii linux-headers-3.16.0-70-generic 3.16.0-70.90~14.04.1 amd64 Linux kernel headers for version 3.16.0 on 64 bit x86 SMP
ii linux-headers-3.16.0-71 3.16.0-71.92~14.04.1 all Header files related to Linux kernel version 3.16.0
ii linux-headers-3.16.0-71-generic 3.16.0-71.92~14.04.1 amd64 Linux kernel headers for version 3.16.0 on 64 bit x86 SMP
ii linux-headers-3.19.0-22 3.19.0-22.22~14.04.1 all Header files related to Linux kernel version 3.19.0
ii linux-headers-3.19.0-22-generic 3.19.0-22.22~14.04.1 amd64 Linux kernel headers for version 3.19.0 on 64 bit x86 SMP
ii linux-headers-3.19.0-23 3.19.0-23.24~14.04.1 all Header files related to Linux kernel version 3.19.0
ii linux-headers-3.19.0-23-generic 3.19.0-23.24~14.04.1 amd64 Linux kernel headers for version 3.19.0 on 64 bit x86 SMP
ii linux-headers-3.19.0-25 3.19.0-25.26~14.04.1 all Header files related to Linux kernel version 3.19.0
ii linux-headers-3.19.0-25-generic 3.19.0-25.26~14.04.1 amd64 Linux kernel headers for version 3.19.0 on 64 bit x86 SMP
ii linux-headers-3.19.0-26 3.19.0-26.28~14.04.1 all Header files related to Linux kernel version 3.19.0
ii linux-headers-3.19.0-26-generic 3.19.0-26.28~14.04.1 amd64 Linux kernel headers for version 3.19.0 on 64 bit x86 SMP
ii linux-headers-3.19.0-28 3.19.0-28.30~14.04.1 all Header files related to Linux kernel version 3.19.0
ii linux-headers-3.19.0-28-generic 3.19.0-28.30~14.04.1 amd64 Linux kernel headers for version 3.19.0 on 64 bit x86 SMP
ii linux-headers-3.19.0-30 3.19.0-30.34~14.04.1 all Header files related to Linux kernel version 3.19.0
ii linux-headers-3.19.0-30-generic 3.19.0-30.34~14.04.1 amd64 Linux kernel headers for version 3.19.0 on 64 bit x86 SMP
ii linux-headers-3.19.0-31 3.19.0-31.36~14.04.1 all Header files related to Linux kernel version 3.19.0
ii linux-headers-3.19.0-31-generic 3.19.0-31.36~14.04.1 amd64 Linux kernel headers for version 3.19.0 on 64 bit x86 SMP
ii linux-headers-3.19.0-32 3.19.0-32.37~14.04.1 all Header files related to Linux kernel version 3.19.0
ii linux-headers-3.19.0-32-generic 3.19.0-32.37~14.04.1 amd64 Linux kernel headers for version 3.19.0 on 64 bit x86 SMP
ii linux-headers-3.19.0-33 3.19.0-33.38~14.04.1 all Header files related to Linux kernel version 3.19.0
ii linux-headers-3.19.0-33-generic 3.19.0-33.38~14.04.1 amd64 Linux kernel headers for version 3.19.0 on 64 bit x86 SMP
ii linux-headers-3.19.0-37 3.19.0-37.42~14.04.1 all Header files related to Linux kernel version 3.19.0
ii linux-headers-3.19.0-37-generic 3.19.0-37.42~14.04.1 amd64 Linux kernel headers for version 3.19.0 on 64 bit x86 SMP
ii linux-headers-3.19.0-39 3.19.0-39.44~14.04.1 all Header files related to Linux kernel version 3.19.0
ii linux-headers-3.19.0-39-generic 3.19.0-39.44~14.04.1 amd64 Linux kernel headers for version 3.19.0 on 64 bit x86 SMP
ii linux-headers-3.19.0-41 3.19.0-41.46~14.04.2 all Header files related to Linux kernel version 3.19.0
ii linux-headers-3.19.0-41-generic 3.19.0-41.46~14.04.2 amd64 Linux kernel headers for version 3.19.0 on 64 bit x86 SMP
ii linux-headers-3.19.0-42 3.19.0-42.48~14.04.1 all Header files related to Linux kernel version 3.19.0
ii linux-headers-3.19.0-42-generic 3.19.0-42.48~14.04.1 amd64 Linux kernel headers for version 3.19.0 on 64 bit x86 SMP
ii linux-headers-3.19.0-43 3.19.0-43.49~14.04.1 all Header files related to Linux kernel version 3.19.0
ii linux-headers-3.19.0-43-generic 3.19.0-43.49~14.04.1 amd64 Linux kernel headers for version 3.19.0 on 64 bit x86 SMP
ii linux-headers-3.19.0-47 3.19.0-47.53~14.04.1 all Header files related to Linux kernel version 3.19.0
ii linux-headers-3.19.0-47-generic 3.19.0-47.53~14.04.1 amd64 Linux kernel headers for version 3.19.0 on 64 bit x86 SMP
ii linux-headers-3.19.0-49 3.19.0-49.55~14.04.1 all Header files related to Linux kernel version 3.19.0
ii linux-headers-3.19.0-49-generic 3.19.0-49.55~14.04.1 amd64 Linux kernel headers for version 3.19.0 on 64 bit x86 SMP
ii linux-headers-3.19.0-51 3.19.0-51.58~14.04.1 all Header files related to Linux kernel version 3.19.0
ii linux-headers-3.19.0-51-generic 3.19.0-51.58~14.04.1 amd64 Linux kernel headers for version 3.19.0 on 64 bit x86 SMP
ii linux-headers-3.19.0-56 3.19.0-56.62~14.04.1 all Header files related to Linux kernel version 3.19.0
ii linux-headers-3.19.0-56-generic 3.19.0-56.62~14.04.1 amd64 Linux kernel headers for version 3.19.0 on 64 bit x86 SMP
ii linux-headers-3.19.0-58 3.19.0-58.64~14.04.1 all Header files related to Linux kernel version 3.19.0
ii linux-headers-3.19.0-58-generic 3.19.0-58.64~14.04.1 amd64 Linux kernel headers for version 3.19.0 on 64 bit x86 SMP
ii linux-headers-3.19.0-59 3.19.0-59.66~14.04.1 all Header files related to Linux kernel version 3.19.0
ii linux-headers-3.19.0-59-generic 3.19.0-59.66~14.04.1 amd64 Linux kernel headers for version 3.19.0 on 64 bit x86 SMP
ii linux-headers-generic 3.13.0.86.92 amd64 Generic Linux kernel headers
ii linux-headers-generic-lts-quantal 3.13.0.86.92 amd64 Generic Linux kernel headers
ii linux-headers-generic-lts-raring 3.13.0.86.92 amd64 Generic Linux kernel headers
ii linux-headers-generic-lts-saucy 3.13.0.86.92 amd64 Generic Linux kernel headers
ii linux-headers-generic-lts-trusty 3.13.0.86.92 amd64 Generic Linux kernel headers
ii linux-headers-generic-lts-utopic 3.16.0.71.62 amd64 Generic Linux kernel headers
ii linux-headers-generic-lts-vivid 3.19.0.59.42 amd64 Generic Linux kernel headers
Why?
As I don't have 3.16 and 3.19 kernels, why does my system downloads and installs all these 3.16 and 3.19 headers?
First, remove the metapackages for Utopic and Vivid:
...then the autoremove command should work:
You may also want to try and remove all headers and kernels but the latest:
dry run, prints out which packages are to be removed
will remove all but the latest kernels, headers and modules
Source and steps