Well I googled lots but didn't come up with the answer. I have however solved the issue by downgrading the DENX uboot to the Marvel version 3.4.19 and now I have managed to get the SD card to boot correctly

To revert wasn't totally straight forward as the tftpboot command would not load the Marvel uboot binary no matter what I did. So, I loaded the u-boot.bin (3.4.19) onto the SD card via SCP so it was available for me to copy from the uboot prompt. Here's the steps I went through:
1) Boot into NAND based Linux
2) Mount the SD card (mkdir /mnt/sdcard; mount /dev/mmcblk0p1 /mnt/sdcard)
3) scp the uboot binary onto the SD card /mnt/sdcard directory
4) Restart the Sheeva and drop into uboot mode
5) Copy the uboot file into memory (ext2load mmc 0:2 0x0800000 u-boot.bin)
6) Clear out the old uboot binary (nand erase 0x0 0x80000)
7) copy the new binary from memory into NAND (nand write 0x0800000 0x0 0x80000) - ensure the memory copy is long enough for the uboot binary

reboot the plug
This downgraded me to 3.4.19 ok. After some env tweaks I got the standard plugpbx build up and running

At least I know it's ok to switch uboot versions easy enough now so this can always be revisited to use the later, and probably better, DENX uboot versions.
I do now hit the issue described here in which I get random junk characters in the console and the console isn't usable, but ssh works fine. I guess this may be fixed with your newer build which I could also try once I have the core system up and running.
http://www.plugcomputer.org/plugforum/index.php?topic=2173.0It may be worth noting on the build pages that users should use the Marvel version of the uboot code and not just follow the hyperlink you provided verbatum!
Thanks for the comments and the great info on the site,
Jed