I started the installer from a USB stick, and installed on a SDHC (a Transcend Class 6 16 GB) card.
I tried the installation two times, and tried booting the Sheevaplug multiple times.
I installed everything in a single partition (although the installer makes a separate boot partition in any case, contra what Martin says in the installation instructions).
I believe Martin's instructions are correct:
"Please note that you may have to replace /uInitrd and /uImage with /boot/uInitrd and /boot/uImage depending on the way you installed Debian. By default, Debian will create a separate boot partition, so the full path to the kernel is /uImage. However, if you choose to put everything on the same partition, you have to use /boot/uImage."
As this is the exact behavior I saw when I used the installer. It did in fact create a separate boot partition formatted as ext2 with the rest of the filesystem in another ext3 partition.
Perhaps then you have the uboot parameters incorrect?