Não consegui encontrar nada, então acho que o script de desligamento foi corrompido. Para consertar eu fiz o seguinte
# which shutdown
/sbin/shutdown
# dpkg-query -S /sbin/shutdown
upstart: /sbin/shutdown
# apt-get install --reinstall upstart
e agora funciona novamente.
Acho que o próximo passo é descobrir por que esses arquivos são corrompidos. Thx pela ajuda