Comment 63 for bug 110636

I've fixed this by switching to IDE drivers.
To do this, append those lines to /etc/initramfs-tools/modules:

atiixp # change to your chipset driver!
ide_core
ide_cd
ide_disk
ide_generic
blacklist ata_generic
blacklist pata_atiixp
blacklist pata_acpi

Maybe you don't need the blacklist stuff, I'm not sure. The chipset driver should be one of those printed by "lsmod | grep permanent".
Then update initramfs by "sudo update-initramfs -u" and change all /dev/sda to /dev/hda in /boot/grub/menu.lst and /etc/fstab. Also probably that UUID stuff should be changed to /dev/hda* too.
Use at your own risk, of course.