Solution 1:

According to womble's answer to Damaged /vmlinuz and /initrd.img symbolic links after Kernel uninstall (on Server Fault), you don't have to do anything in this situation when your boot loader is GRUB/GRUB2—which it is, here.

For some other boot loaders (at least LILO), it is/was apparently sometimes necessary to manually run the boot loader's configuration.

If you did need to tell GRUB to check for existing kernels and update its configuration, running sudo update-grub would do so. And there's no harm in running that. But it shouldn't be necessary in this case.

Solution 2:

The error is a bit odd in case of grub.

When apt installs a new kernel-version, it moves /vmlinuz and /initrd.img to /vmlinuz.old and /initrd.img.old (Which then are still pointing to the currently active kernel. Again, notice the .old extension, which is different from the story linked in "Damaged links after kernel uninstall") and creates two new files /vmlinuz /initrd.img.

When you run apt-get autoremove (the messages weren't generated by apt-get -f install) it removes that previously active kernel (you rebooted after that install, before running autoremove, right?), which makes the links invalid.

When the removal of the kernel itself done, the autoremove itself invokes update-grub:

run-parts: executing /etc/kernel/postrm.d/zz-update-grub 3.13.0-32-generic /boot/vmlinuz-3.13.0-32-generic

Hence:

The link /vmlinuz.old is a damaged link
Removing symbolic link vmlinuz.old 
 you may need to re-run your boot loader[grub]

So, autoremove does:

  1. remove old kernel
  2. run update-grub
  3. update-grub removes .old files which linked to removed files.

Nothing to worry about :-)

Regards.

Solution 3:

$ sudo update-grub

And if you want delete / purge old packages you can do also

$ dpkg --list |grep "^rc" | cut -d " " -f 3 | xargs sudo dpkg --purge