I haven't had your problem, but I know of a good way to reburn your ROM.  The installer utility (http://www.openplug.org/index.php/us/resources/downloads?func=fileinfo&id=53) will reflash the bootloader (uboot), kernel and filesystem.  I've used it a number of times with good results.  I reflash using a Linux host, but the documentation says the installer works on Windows as well (other users have reported success with a Windows host).  It won't get you back to the original state, as the included files are more recent builds, but they have worked better than the originals for me (the originals had a number of warnings on power up, and they were probably 3-4 times slower to boot).

I just ran the V1.0 Installer on my Sheeva which gets it to version 2.6.30.2.  Once you get through that (see other threads), getting the 2.6.31 kernel going was very easy.  Download the README-2.6.31 file to your Sheeva, make it executable and type:
./README-2.6.31 --nandkernel

Wait for the files to be downloaded and a re-flash.

Reboot and wait for the Sheeva to come up.

Type
uname -a

and you'll get
Linux ubuntu 2.6.31 #2 PREEMPT Wed Sep 16 00:55:42 MDT 2009 armv5tel GNU/Linux

I haven't run any extensive tests, but the application I run and ssh runs without a hitch.

Nice work and thanks to all!