Bug#377423: Similar problem
I have also experienced this problem on 2.6.18 through 2.6.22 (amd64). I have an internal SATA drive with my Debian installation on it and an external eSATA drive with documents and such. The eSATA drive was incorrectly chosen as /dev/sda on approximately 75% of boots, which resulted in the kernel failing to find "init". See the bug that I opened at kernel.org: http://bugzilla.kernel.org/show_bug.cgi?id=8935
I have used Christian's recommended workaround, but it would be nice for it to have not been necessary. As the kernel developer that answered the above bug said, the problem is that Debian's initrd has indeterminate module loading order: ata_piix is sometimes loaded before ahci, and sometimes the opposite. If it is feasible to _automatically_ constrain the module loading order so that this does not happen, then it would be desirable to do that. Failing that, though, I support Christian's suggestion to include the options he mentioned in partman, with the default being uuid like in Ubuntu.
Reply to: