“checking if image is initramfs… it isn’t (bad gzip magic numbers)”

If your initramfs grew too big (Hardy 8.04 Ubuntu, anyone?) and you use LILO because your /boot partition is in a LVM, you must add the line below to /etc/lilo.conf and re-run /sbin/lilo:

large-memory