I have found that on the minimal virtual machine that you can have on AWS (includes the free setup) has a small /boot size and this can quickly become full as new kernels are installed, especially when they are automatically installed.
When you run out of space, the install will fail, and this will confuse the
apt-get autoremove command so that old kernels cannot be removed (it also affects other installs/removals also).
After a good hunt around, I found the best instructions to fix this problem are here:
It is very important to not delete your existing running kernel, hence the
uname -r command at the beginning. Write this release number down and regularly check it before you start deleting each kernel.
And also, the auto complete double TAB TAB works well in checking the release number for each Linux and header packages.