Tente isto para cada pacote linux-image-extra- *:
dpkg --purge --force-depends linux-image-extra-3.16.0-34-generic
Se isso não funcionar, você pode tentar superar os logs ERRO e FATAL gerando os arquivos ausentes com
touch /boot/System.map-3.16.0-34-generic