Existe um arquivo mágico. Se existir, isso sinaliza que uma reinicialização é necessária. Seu caminho é:
/var/run/reboot-required
Tente excluir esse arquivo como root e informe se é possível excluí-lo. Se for possível apagá-lo, verifique se o problema desapareceu.