Having updated the kernel to 126.96.36.199 everything is now working. I do have a plug that is running Debian from the nand with UBIFS.
After I figured how to update the kernel I started with a complete new installation of Debian on USB drive following the instructions in the Wiki (http://www.plugcomputer.org/plugwiki/index.php/Installing_Debian_To_Flash
If you update the kernel before converting internal flash root partition to UBIFS I could even use
ubiformat /dev/mtd2 -s 512
ubiattach /dev/ubi_ctrl -m 2
ubimkvol /dev/ubi0 -N rootfs -m
mount -t ubifs ubi0:rootfs /mnt
without any problem.
The only thing that didn't work from that manual was the setup of the boot loader. For that point I found some useful instructions at http://www.jukie.net/~bart/blog/20100215083725
The ultimate problem then was that the sheeva stopped booting after uncompressing the kernel. I solved this by reentering
setenv mainlineLinux yes
setenv arcNumber 2097
Thanks for your help.