Ok, I'll take some of my comments back.  The problem lies in the init scripts and the sequence numbers / priorities on the link.  On my upgraded systems, /etc/rc0.d looks like this:
lrwxrwxrwx 1 root root  26 2010-04-13 12:51 K01clamav-freshclam -> ../init.d/clamav-freshclam
lrwxrwxrwx 1 root root  16 2010-04-13 12:51 K01dhcdbd -> ../init.d/dhcdbd
lrwxrwxrwx 1 root root  16 2010-05-20 15:21 K01distcc -> ../init.d/distcc
lrwxrwxrwx 1 root root  14 2010-04-13 12:51 K01ferm -> ../init.d/ferm
lrwxrwxrwx 1 root root  17 2010-04-13 12:51 K01hddtemp -> ../init.d/hddtemp
lrwxrwxrwx 1 root root  20 2010-04-13 12:51 K01kerneloops -> ../init.d/kerneloops
lrwxrwxrwx 1 root root  21 2010-04-13 12:51 K01laptop-mode -> ../init.d/laptop-mode
lrwxrwxrwx 1 root root  15 2010-04-13 12:51 K01mdadm -> ../init.d/mdadm
lrwxrwxrwx 1 root root  27 2010-04-13 12:51 K01nfs-kernel-server -> ../init.d/nfs-kernel-server
lrwxrwxrwx 1 root root  18 2009-10-07 10:37 K01nxsensor -> ../init.d/nxsensor
lrwxrwxrwx 1 root root  18 2009-10-07 10:37 K01nxserver -> ../init.d/nxserver
lrwxrwxrwx 1 root root  23 2010-04-13 12:51 K01openbsd-inetd -> ../init.d/openbsd-inetd
lrwxrwxrwx 1 root root  17 2010-04-13 12:51 K01openvpn -> ../init.d/openvpn
lrwxrwxrwx 1 root root  17 2010-04-13 12:51 K01postfix -> ../init.d/postfix
lrwxrwxrwx 1 root root  14 2010-04-13 12:51 K01vtun -> ../init.d/vtun
lrwxrwxrwx 1 root root  17 2010-04-13 12:51 K01winbind -> ../init.d/winbind
lrwxrwxrwx 1 root root  13 2010-05-20 15:01 K01xdm -> ../init.d/xdm
lrwxrwxrwx 1 root root  15 2010-04-13 12:51 K02mysql -> ../init.d/mysql
lrwxrwxrwx 1 root root  19 2010-04-13 12:51 K03mysql-ndb -> ../init.d/mysql-ndb
lrwxrwxrwx 1 root root  23 2010-04-13 12:51 K04mysql-ndb-mgm -> ../init.d/mysql-ndb-mgm
lrwxrwxrwx 1 root root  17 2010-05-20 15:21 K08apache2 -> ../init.d/apache2
-rw-r--r-- 1 root root 353 2009-09-08 04:58 README
lrwxrwxrwx 1 root root  14 2010-04-13 12:51 S01halt -> ../init.d/halt
lrwxrwxrwx 1 root root  20 2010-05-20 15:01 S01networking -> ../init.d/networking
lrwxrwxrwx 1 root root  18 2010-04-13 12:51 S01sendsigs -> ../init.d/sendsigs
lrwxrwxrwx 1 root root  18 2010-04-13 12:51 S01umountfs -> ../init.d/umountfs
lrwxrwxrwx 1 root root  22 2010-04-13 12:51 S01umountnfs.sh -> ../init.d/umountnfs.sh
lrwxrwxrwx 1 root root  20 2010-04-13 12:51 S01umountroot -> ../init.d/umountroot
lrwxrwxrwx 1 root root  29 2010-04-13 12:51 S01unattended-upgrades -> ../init.d/unattended-upgrades
lrwxrwxrwx 1 root root  17 2010-05-20 15:01 S02urandom -> ../init.d/urandom
lrwxrwxrwx 1 root root  22 2010-04-13 12:51 S02wpa-ifupdown -> ../init.d/wpa-ifupdown
lrwxrwxrwx 1 root root  26 2010-05-20 15:01 S04cryptdisks-early -> ../init.d/cryptdisks-early
lrwxrwxrwx 1 root root  20 2010-05-20 15:01 S06cryptdisks -> ../init.d/cryptdisks


On a fresh install it looks like this:
lrwxrwxrwx 1 root root  24 2010-05-20 21:30 K08vmware-tools -> /etc/init.d/vmware-tools
lrwxrwxrwx 1 root root  19 2010-05-20 21:14 K74bluetooth -> ../init.d/bluetooth
-rw-r--r-- 1 root root 353 2009-09-07 11:58 README
lrwxrwxrwx 1 root root  29 2010-05-20 21:14 S10unattended-upgrades -> ../init.d/unattended-upgrades
lrwxrwxrwx 1 root root  22 2010-05-20 21:14 S15wpa-ifupdown -> ../init.d/wpa-ifupdown
lrwxrwxrwx 1 root root  18 2010-05-20 21:14 S20sendsigs -> ../init.d/sendsigs
lrwxrwxrwx 1 root root  17 2010-05-20 21:14 S30urandom -> ../init.d/urandom
lrwxrwxrwx 1 root root  22 2010-05-20 21:14 S31umountnfs.sh -> ../init.d/umountnfs.sh
lrwxrwxrwx 1 root root  20 2010-05-20 21:14 S35networking -> ../init.d/networking
lrwxrwxrwx 1 root root  18 2010-05-20 21:14 S40umountfs -> ../init.d/umountfs
lrwxrwxrwx 1 root root  20 2010-05-20 21:14 S60umountroot -> ../init.d/umountroot
lrwxrwxrwx 1 root root  14 2010-05-20 21:14 S90halt -> ../init.d/halt


In the upgraded system, I suspect halt is being run very early as is at sequence number 01.Working out which package is responsible for this is beyond me.  I've tried to fixing the sequence numbers to be the same as the fresh install but that hasn't helped either.