Have you tried booting into different run levels?
From DSL(Damn Small Linux)I tried booting with various options, and run levels and the system will just hang at the same place rather than reboot. The odd thing about that is DSL runs from the CDROM, and doesn't utilize the hard disk as far as I know.
I'm just wondering what they could have possibly changed in the BIOS with that update that would cause Linux do such a thing.