История кстати управляет

Это могло быть совпадением, но все ошибки имеют отношение к вызову программ в /usr/sbin: update-info-dir, update-rc.d, locale-gen, update-dictcommon-aspell, grub-mkdevicemap, grub-probe, grub-install, update-grub, update-initramfs, update-rc.d, а также invoke-rc.d от bluezprerm все живут в /usr/sbin.

Первая вещь проверить состоит в том ли /usr/sbin в корне PATH, но это вряд ли будет проблема потому что dpkg обычно жалуется громко, если это не. На самом деле, со сжатия, dpkg жалуется громко, если это не может найти update-rc.d в PATH, таким образом, странно что rsyslog postinst не может найти этот исполняемый файл даже при том, что dpkg не жалуется.

Что происходит, если Вы выполняете эти команды (как корень)?

type update-rc.d
ls -l /usr/sbin/update-rc.d
file /usr/sbin/update-rc.d
update-rc.d --help
file /bin/sh

Результат этих команд может предложить фиксацию. Если Вы находите интересными, ведет, но испытайте затруднения при выяснении того, что они имеют в виду, отредактируйте вопрос добавить эту информацию. Также сообщите о чем-либо “необычном” о своей системе (SELinux, chroot, установка двойной архитектуры, …).