Sounds like the update is moving boot files. You could try re-running grub-install after doing the install to update the bootloader's map of where the kernel and initrd are. Be careful, messing with bootloaders is a quick way to an un-bootable system. Check your /boot/grub/menu.lst file, and check the first boot section. For my install of Ubuntu 8.10, it looks like this: (near the bottom)
title Ubuntu 8.10, kernel 2.6.27-9-generic
kernel /boot/vmlinuz-2.6.27-9-generic root=UUID=cef4174e-92f8-484d-a63f-3b0bc9274a9a ro quiet splash
AFTER running the update, verify that the files listed as kernel and initrd exist. Then, check your root filesystem's UUID:
sudo vol_id --uuid /dev/[ROOT DEVICE]
The hex string you get back should match the uuid string in the menu.lst file. If those things are correct, try running grub-install to reinstall the bootloader.