O.K. I played a bit with it and finally it started to work. On 2 different SheevaPlug. (1 of them with bad block during the formating).
The trick was to ignore (and do not even try) ubiattach after flashing new UBI immage on the NAND. I just run: <br>
ubiformat /dev/mtd2 -s 512 -f /tmp/ubi.img
<br>
and the restarted the SheevaPlug with rootfs from nand. In one case the fsck was automatically started to fix some problems, in second case it was running straightforward.
So I have finally 2 SheevaPlugs with Debian running.

There are still some minor issues, but it WORKS.

BTW, after first reboot (and very likely some fixes of FS) of Sheeva NAND  system I was able to attach and mount UBIFS when I booted from USB again (still ro only). So I have feeling there are some issues with mkfs.ubifs or ubinize ....

Hi, I have exactly the same problem. And I am relatively sure I booted from the SD card.
Here what's happening:
root@sheeva:~# uname -r
2.6.32-trunk-kirkwood
root@sheeva:~# dmesg |less
[    0.000000] Initializing cgroup subsys cpuset
[    0.000000] Initializing cgroup subsys cpu
[    0.000000] Linux version 2.6.32-trunk-kirkwood (Debian 2.6.32-5) (ben@decadent.org.uk) (gcc version 4.3.4 (Debian 4.3.4-6) ) #1 Mon Jan 11 10:57:12 UTC0
[    0.000000] CPU: Feroceon 88FR131 [56251311] revision 1 (ARMv5TE), cr=00053977
[    0.000000] CPU: VIVT data cache, VIVT instruction cache
[    0.000000] Machine: Marvell SheevaPlug Reference Board
[    0.000000] Memory policy: ECC disabled, Data cache writeback
[    0.000000] On node 0 totalpages: 131072
[    0.000000] free_area_init_node: node 0, pgdat c03d0904, node_mem_map c0cda000
[    0.000000]   Normal zone: 1024 pages used for memmap
[    0.000000]   Normal zone: 0 pages reserved
[    0.000000]   Normal zone: 130048 pages, LIFO batch:31
[    0.000000] Built 1 zonelists in Zone order, mobility grouping on.  Total pages: 130048
[    0.000000] Kernel command line: console=ttyS0,115200
[    0.000000] PID hash table entries: 2048 (order: 1, 8192 bytes)
[    0.000000] Dentry cache hash table entries: 65536 (order: 6, 262144 bytes)
[    0.000000] Inode-cache hash table entries: 32768 (order: 5, 131072 bytes)
[    0.000000] Memory: 256MB 256MB = 512MB total
root@sheeva:~# ubidetach /dev/ubi_ctrl -m 2                                                                                                                 
[ 1220.656760] UBI: mtd2 is detached from ubi0
root@sheeva:~# ubiformat /dev/mtd2 -s 512
ubiformat: mtd2 (nand), size 531628032 bytes (507.0 MiB), 4056 eraseblocks of 131072 bytes (128.0 KiB), min. I/O size 2048 bytes
libscan: scanning eraseblock 76 --  1 % complete   2
libscan: scanning eraseblock 4055 -- 100 % complete 
ubiformat: 4053 eraseblocks have valid erase counter, mean value is 1
ubiformat: 1 eraseblocks are supposedly empty
ubiformat: bad eraseblocks: 166, 2366
ubiformat: formatting eraseblock 4055 -- 100 % complete 
root@sheeva:~#    ubiattach /dev/ubi_ctrl -m 2
[ 1271.664780] UBI: attaching mtd2 to ubi0
[ 1271.668637] UBI: physical eraseblock size:   131072 bytes (128 KiB)
[ 1271.674970] UBI: logical eraseblock size:    129024 bytes
[ 1271.680389] UBI: smallest flash I/O unit:    2048
[ 1271.685127] UBI: sub-page size:              512
[ 1271.689764] UBI: VID header offset:          512 (aligned 512)
[ 1271.695632] UBI: data offset:                2048
[ 1272.107616] UBI: attached mtd2 to ubi0
[ 1272.111420] UBI: MTD device name:            "root"
[ 1272.116320] UBI: MTD device size:            507 MiB
[ 1272.121320] UBI: number of good PEBs:        4054
[ 1272.126042] UBI: number of bad PEBs:         2
[ 1272.130506] UBI: max. allowed volumes:       128
[ 1272.135156] UBI: wear-leveling threshold:    4096
[ 1272.139880] UBI: number of internal volumes: 1
[ 1272.144355] UBI: number of user volumes:     0
[ 1272.148818] UBI: available PEBs:             4010
[ 1272.153554] UBI: total number of reserved PEBs: 44
[ 1272.158367] UBI: number of PEBs reserved for bad PEB handling: 40
[ 1272.164499] UBI: max/mean erase counter: 12/2
[ 1272.168874] UBI: image sequence number: 0
[ 1272.173754] UBI: background thread "ubi_bgt0d" started, PID 1047
UBI device number 0, total 4054 LEBs (523063296 bytes, 498.8 MiB), available 4010 LEBs (517386240 bytes, 493.4 MiB), LEB size 129024 bytes (126.0 KiB)
root@sheeva:~# ubimkvol /dev/ubi0 -N rootfs -m
Set volume size to 517386240
[ 1286.379273] UBI error: ubi_io_write: error -5 while writing 512 bytes to PEB 0:512, written 0 bytes
[ 1286.388397] UBI warning: ubi_eba_write_leb: failed to write VID header to LEB 2147479551:0, PEB 0
[ 1286.398034] UBI: try another PEB
[ 1286.401461] UBI: run torture test for PEB 0
[ 1286.406244] UBI error: ubi_io_write: error -5 while writing 512 bytes to PEB 4055:512, written 0 bytes
[ 1286.415618] UBI warning: ubi_eba_write_leb: failed to write VID header to LEB 2147479551:0, PEB 4055
[ 1286.451400] UBI: try another PEB
[ 1286.630962] UBI: PEB 0 passed torture test, do not mark it a bad
[ 1286.639260] UBI error: ubi_io_write: error -5 while writing 512 bytes to PEB 4052:512, written 0 bytes
[ 1286.648637] UBI warning: ubi_eba_write_leb: failed to write VID header to LEB 2147479551:0, PEB 4052
[ 1286.658330] UBI: run torture test for PEB 4055
[ 1286.681622] UBI: try another PEB
[ 1286.864542] UBI: PEB 4055 passed torture test, do not mark it a bad
[ 1286.873033] UBI error: ubi_io_write: error -5 while writing 512 bytes to PEB 0:512, written 0 bytes
[ 1286.882151] UBI warning: ubi_eba_write_leb: failed to write VID header to LEB 2147479551:0, PEB 0
[ 1286.891702] UBI: run torture test for PEB 4052
[ 1286.908047] UBI warning: ubi_ro_mode: switch to read-only mode
[ 1286.922099] UBI error: ubi_create_volume: cannot create volume 0, error -30
ubimkvol: error!: cannot UBI create volume
          error 30 (Read-only file system)
root@sheeva:~# [ 1286.990259] UBI error: ubi_io_write: read-only mode
[ 1286.995188] UBI error: erase_worker: failed to erase PEB 4052, error -30
[ 1287.001932] UBI error: do_work: work failed with error code -30
[ 1287.007884] UBI error: ubi_thread: ubi_bgt0d: work failed with error code -30

root@sheeva:~# ls /mnt/
root@sheeva:~# mount -t ubifs ubi0:rootfs /mnt
[ 1302.236814] UBIFS error (pid 1050): ubifs_get_sb: cannot open "ubi0:rootfs", error -19
mount: unknown filesystem type 'ubifs'
root@sheeva:~#
root@sheeva:~# mount
rootfs on / type rootfs (rw)
none on /sys type sysfs (rw,nosuid,nodev,noexec,relatime)
none on /proc type proc (rw,nosuid,nodev,noexec,relatime)
udev on /dev type tmpfs (rw,relatime,size=10240k,mode=755)
/dev/disk/by-uuid/868f3fab-0151-445f-a6ea-993b29ad39b2 on / type ext3 (rw,relatime,errors=remount-ro,data=ordered)
tmpfs on /lib/init/rw type tmpfs (rw,nosuid,relatime,mode=755)
tmpfs on /dev/shm type tmpfs (rw,nosuid,nodev,relatime)
devpts on /dev/pts type devpts (rw,nosuid,noexec,relatime,gid=5,mode=620,ptmxmode=000)
/dev/mmcblk0p1 on /boot type ext2 (rw,relatime,errors=continue)

I just followed the debian instalation process on SD card. And now I would like to transfer my system to flash.

thanks for any hint

Dodiak ...