Have you built-in drivers for the video card, or left them as loadable modules? It is possible that you built something into the kernel that is failing when the card isn't present, but it still does seem a little odd. The kernel shouldn't crash just because a piece of hardware isn't inserted, even if the driver is built in...
You might want to try setting up a serial terminal and watching the boot process from another machine. That may give you a clue as to were the failure is occurring.
has information about configuring LILO (and through that, the kernel) to output over serial.