Этого не может быть, поэтому рассказывай всё от начала и до конца.
Содержимое /var/log/user/info, весь вывод в stdout и stderr, содержимое и timestamp файла /etc/sysconfig/installkernel до и после обновления, и т.д. и т.п.

Этого "не может быть" у меня уже на четырёх серверах.

до обновления:
# cat /etc/sysconfig/installkernel 
INITRD_GENERATOR=make-initrd
MKINITRD=/usr/sbin/mkinitrd-make-initrd

# ls -al /etc/sysconfig/installkernel 
-rw-r--r-- 1 root root 69 Sep 19 09:37 /etc/sysconfig/installkernel


Делаю dist-upgrade (большой), после него:

# cat /etc/sysconfig/installkernel
#INITRD_GENERATOR=make-initrd
#MKINITRD=/usr/sbin/mkinitrd-make-initrd
#INITRD_AUTOUPDATE=all

# ls -al /etc/sysconfig/installkernel
-rw-r--r-- 1 root root 94 Dec 11 23:42 /etc/sysconfig/installkernel

В /var/log/user/info всё красиво:
Dec 11 23:42:32 dns2 apt-get: make-initrd-0.4.3-alt2 installed 
Dec 11 23:42:33 dns2 apt-get: make-initrd-0.3.9-alt1 removed 
Dec 11 23:42:34 dns2 apt-get: bootloader-utils-0.4.11-alt1 installed 
Dec 11 23:42:34 dns2 apt-get: bootloader-utils-0.4.8-alt3 removed 

diff --git a/sysconfig/installkernel b/sysconfig/installkernel
index 2d400f6..7e9d2ae 100644
--- a/sysconfig/installkernel
+++ b/sysconfig/installkernel
@@ -1,2 +1,3 @@
-INITRD_GENERATOR=make-initrd
-MKINITRD=/usr/sbin/mkinitrd-make-initrd
+#INITRD_GENERATOR=make-initrd
+#MKINITRD=/usr/sbin/mkinitrd-make-initrd
+#INITRD_AUTOUPDATE=all


Что ещё надо ?

Да, только что обновил ещё два сервера - всё воспроизводится 100%.

Дима, конечно же оно будет воспроизводится, там же явно в скрипте написано:
preinstall scriptlet (through /bin/sh):
[ $1 -gt 1 ] || exit 0
f=/etc/sysconfig/installkernel
rm -f $f.install
[ ! -f $f ] || exit 0
if [ ! -f $f.rpmsave ]; then
cat > $f.install <<-EOF
#INITRD_GENERATOR=make-initrd
#MKINITRD=/usr/sbin/mkinitrd-make-initrd
#INITRD_AUTOUPDATE=all
EOF
else
  cp -a $f.rpmsave $f.install
fi

Если нет rpmsave, тогда в $f.install нагенерить комментариев.

а далее:
postinstall scriptlet (through /bin/sh):
[ $1 -gt 1 ] || exit 0
f=/etc/sysconfig/installkernel
[ -f $f.install ] || exit 0
cp -a $f $f.rpmnew 2> /dev/null ||:
mv $f.install $f

если этот $f.install есть (а его не может не есть), то нужно срочно $f переименовать в $f.rpmnew, а $f.install в $f

что-то в этом алгоритме всё не так ;(

Воспроизводится. Тож самое делал, загрузился со старым ядром. После оказалось что в системе отсутствовал mkinitrd. Как я раньше жил? видимо снесло недавно. Далее сделал apt-get --reinstall нового ядра. initrd создался автоматически

(In reply to comment #4)
> Дима, конечно же оно будет воспроизводится, там же явно в скрипте написано:
> preinstall scriptlet (through /bin/sh):
> [ $1 -gt 1 ] || exit 0
> f=/etc/sysconfig/installkernel
> rm -f $f.install
> [ ! -f $f ] || exit 0
> if [ ! -f $f.rpmsave ]; then
> cat > $f.install <<-EOF
> #INITRD_GENERATOR=make-initrd
> #MKINITRD=/usr/sbin/mkinitrd-make-initrd
> #INITRD_AUTOUPDATE=all
> EOF

Здесь логическая ошибка:

# Neither installkernel nor installkernel.rpmsave exits, no way to find
# out whether the vanilla installkernel existed before the start of our
# transaction and we should reinstall it in %%post, or no installkernel
# existed at all and we should install a mkinitrd-compatible installkernel.

Я вижу только один способ стабильного решения проблемы -- поменять порядок обновления на противоположный: в bootloader-utils поменять prereq на requires, а в make-initrd поменять requires на prereq.  Альтернативно -- забить на поддержку mkinitrd при миграции installkernel.

Ладно, поскольку кого-то все равно придется принести в жертву, принесем в жертву пользователей mkinitrd.

bootloader-utils-0.4.12-alt1 -> sisyphus:

* Sun Dec 12 2010 Dmitry V. Levin <ldv@altlinux> 0.4.12-alt1
- %pre: when neither /etc/sysconfig/installkernel nor
  /etc/sysconfig/installkernel.rpmsave exists, assume that
  system was configured to use make-initrd (closes: #24739),
  and issue a warning for mkinitrd users.