Check that you got both the linux-image and the header files. You should not
have to update-grub if the kernel modules are removed fully. It is part of
the removal process. If you open the terminal in the removing packages
window it will show you the complete process. I always have it open so I can
see what goes on behind the scenes, but by default it is hidden.

Failing this you can go with Ian's tried and true method. But that is only
cosmetic if the kernel packages are still on your computer. I am not sure
what else to say. I just removed two of my older kernels and it worked
fine.