This is still happening on 8.04; every kernel upgrade we do (via apt-get dist-upgrade) gives these lilo errors.  We are fully lvm, with a separate lvm boot partition.  For instance after today's apt-get dist-upgrade that updated the kernel and initramfs:

update-initramfs: Generating /boot/initrd.img-2.6.24-19-server
Warning: LBA32 addressing assumed
Warning: '/proc/partitions' does not match '/dev' directory structure.
   Name change: '/dev/dm-0' -> '/dev/vg1/lv1'
Warning: Name change: '/dev/dm-1' -> '/dev/vg1/lv2'
Warning: Name change: '/dev/dm-2' -> '/dev/vg1/lv3'
Added Linux *
Added LinuxOLD
The Master boot record of  /dev/sda  has been updated.
Warning: /dev/sdb is not on the first disk
The Master boot record of  /dev/sdb  has been updated.

% df
Filesystem            Size  Used Avail Use% Mounted on
/dev/mapper/vg1-lv3   461G   43G  395G  10% /
...
/dev/mapper/vg1-lv1   101M   64M   33M  67% /boot


lilo.conf bits:
boot=/dev/md0
raid-extra-boot=mbr-only
image=/vmlinuz
        label=Linux
        read-only
        append="root=/dev/mapper/vg1-lv3  "
        initrd=/initrd.img


% sudo vgdisplay -v
    Finding all volume groups
    Finding volume group "vg1"
  --- Volume group ---
  VG Name               vg1
  System ID
  Format                lvm2
  Metadata Areas        1
  Metadata Sequence No  24
  VG Access             read/write
  VG Status             resizable
  MAX LV                0
  Cur LV                3
  Open LV               3
  Max PV                0
  Cur PV                1
  Act PV                1
  VG Size               465.76 GB
  PE Size               4.00 MB
  Total PE              119234
  Alloc PE / Size       119234 / 465.76 GB
  Free  PE / Size       0 / 0
  VG UUID               G3cY9t-MZDF-ghxc-xkdG-k5Zq-gfsj-be8CG8

  --- Logical volume ---
  LV Name                /dev/vg1/lv1
  VG Name                vg1
  LV UUID                BikR2Q-jjnM-2TbL-h1eQ-JwtD-36IC-IflP2h
  LV Write Access        read/write
  LV Status              available
  # open                 1
  LV Size                104.00 MB
  Current LE             26
  Segments               1
  Allocation             inherit
  Read ahead sectors     0
  Block device           254:0

  --- Logical volume ---
  LV Name                /dev/vg1/lv2
  VG Name                vg1
  LV UUID                vCy8ea-ZC4C-VpCb-S1NV-w0lj-d0LB-URlJQP
  LV Write Access        read/write
  LV Status              available
  # open                 2
  LV Size                1.95 GB
  Current LE             500
  Segments               1
  Allocation             inherit
  Read ahead sectors     0
  Block device           254:1

  --- Logical volume ---
  LV Name                /dev/vg1/lv3
  VG Name                vg1
  LV UUID                uSdl3j-Wk2p-WH8G-5IGH-thG0-MTdE-KPGq6H
  LV Write Access        read/write
  LV Status              available
  # open                 1
  LV Size                463.70 GB
  Current LE             118708
  Segments               1
  Allocation             inherit
  Read ahead sectors     0
  Block device           254:2

  --- Physical volumes ---
  PV Name               /dev/md0
  PV UUID               EJ222m-fxth-xR5T-9YLa-D2Lx-fq2A-l0hqQC
  PV Status             allocatable
  Total PE / Free PE    119234 / 0