Damaged /vmlinuz and /initrd.img symbolic links after Kernel uninstall

Solution 1:

Those messages are nothing to worry about. The symlinks that are being complained about are only needed if you're using lilo as your bootloader, because it uses those symlinks to find your "current" kernel. Grub, being more flexible, has it's own way of doing things, and doesn't need the symlinks.

Solution 2:

You shouldn't need to re-run grub. You would, but after a kernel change you may need to run /usr/sbin/update-grub.

Those messages probably do not indicate an issue. The real test would be to simply reboot the computer. If it boots fine, then nothing bad happened.

You may want to update your /etc/kernel-img.conf and disable the do_symlinks option, and you shouldn't see this message again.