$ dpkg -S /sbin/shutdown
sysvinit-core: /sbin/shutdown
Você provavelmente "atualizou" para systemd , removendo shutdown e amigos. Se assim for, você precisa fazer systemctl poweroff para desligar o sistema. Por que o systemd não fornece um alias para o encerramento? Por que não, de fato ...
EDITAR:
/sbin/shutdown deve estar disponível se você instalar o pacote systemd-sysv . Seria bom se systemd recomendasse ou mesmo apenas sugerisse systemd-sysv .