I ran into the same trouble and I solved it this way:
First download this
http://www.plugcomputer.org/index.php/us/resources/downloads?func=select&id=5 and read the Readme file that explains how the installer works.
Note that if you are using windows to flash the plug it must be a 32bits Windows, won't work otherwise, I had to install XP as a virtual machine myself to get it to work.
In the uboot/uboot-env folder modifiy the uboot-nand-custom.txt file to look like this: (this will give you a multi-boot plug)
#### Change ONLY in the following few lines
# Following for installation on SD card. If you want to boot from USB stick change it to /dev/sda1
# or /dev/mtdblock1 if you installed rootfs on the NAND inside the plug
bootargs_root ubi.mtd=1 root=ubi0:rootfs rootfstype=ubifs
# NAND flash partitions. If using kernel >= 2.6.30 then replace orion_nand with orion_mtd
mtdpartitions mtdparts=orion_nand:0x400000@0x100000(uImage),0x1fb00000@0x500000(rootfs)
# The following is an example MAC address. Change it according the MAC on the back side of the plug
ethaddr XX:XX:XX:XX:XX:XX
#### DONT change the following.
# Automated process the sets arcNumer to 2678, reset, runs uImage and initrd from USB stick and set bootcmd to 'real_bootcmd' above
# Bootcmd to be used after all installation is done
# New IT commented out 2009-11-18 real_bootcmd setenv bootargs $(bootargs_console) $(mtdpartitions) $(bootargs_root); nand read.e 0x00800000 0x00100000 0x00400000; bootm 0x00800000
bootargs_console console=ttyS0,115200
bootcmd run recover1
recover1 setenv mainlineLinux yes; setenv arcNumber 2678; setenv bootcmd run recover2; saveenv; reset
recover2 run recover3; setenv bootcmd $(real_bootcmd); saveenv; setenv bootargs $(bootargs_console) $(mtdpartitions) root=/dev/ram0 rw ramdisk=0x01100000,8M install_type=nand; bootm 0x00800000 0x01100000
recover3 run recover4; nand erase clean 0x00100000 0x00400000; nand write.e 0x00800000 0x00100000 0x00400000
recover4 usb start; fatload usb 0 0x00800000 uImage; fatload usb 0 0x01100000 initrd
bootargs_root_nand ubi.mtd=1 root=ubi0:rootfs rootfstype=ubifs
bootcmd_nand setenv bootargs $(bootargs_console) $(mtdpartitions) $(bootargs_root_nand); nand read.e 0x00800000 0x00100000 0x00400000; bootm 0x00800000
bootargs_root_mmc root=/dev/mmcblk0p2 rootdelay=5
bootcmd_mmc setenv bootargs $(bootargs_console) $(bootargs_root_mmc); mmcinit; ext2load mmc 0:1 0x800000 /uImage; bootm 0x00800000
real_bootcmd run bootcmd_mmc; run bootcmd_nand
Make sure you fill in your plug's MAC address in place of the XX:XX:XX:XX:XX:XX
Now download a kernel and modules from here :
http://sheeva.with-linux.com/sheeva/2.6.38/and put them at the root of a USB stick formatted in FAT16 or FAT32 and rename the kernel to be uImage and the modules to be modules.tar.gz.
Now download this :
http://www.newit.co.uk/rootfs/rootfs-debian-6.0-squeeze-NewIT-v1.5/ and put it on the USB stick as well and rename it rootfs.tar.gz.
Grab the file initrd from the sheevaplug installer "installer" directory and put it on the USB stick as well.
you should now have on the stick: initrd, modules.tar.gz, rootfs.tar.gz, uImage.
Now run the installer per the instructions given in the README.txt file found in the intaller package root directory. Note that you need to add the type of install you want to perform after the excutable. So if you are using windows and since you want to reflash the nand you must use "runme.exe nand" (without the quotes).
Once Uboot has been reflashed (see correct completion signs in the README.txt) close the executable, plug in the stick onto the plug, reset power on the plug, open a console quickly and interupt the Uboot sequence to get the Uboot prompt then type "run recover1". Wait for the process to complete, the plug will reboot and if all went well you will be presented with the squeeze logging prompt.
I hope this is clear and it actually helps.