Como bien dice el mensaje, la partición que no encuentra (y que por tanto no puede formatear) es la que se montará en /data, que es la segunda partición de la flash de 16G. La primera tiene 13.5Gb y es la que se monta en /sdcard.
La solución sería crearla, pero no se si el recovery tiene una opción para eso, búscala y si la encuentras es la solución más fácil.
Si eso no funciona habría que crearla con fdisk, pero creo que android (y por tanto el recovery) no tienen dicha utilidad, de modo que una opción es hacerlo desde Linux, seguro que hay un tutorial de desdelsur que explica como hacerlo.
Una vez que tengas el linux funcionando, sacas un terminal y escribes:
$ sudo su
te pedirá el password del usuario de instalación (en mi caso user).
# fdisk /dev/mmcblk1
y cuando te pida un comando pulsa p (para escribir las particiones), en mi caso sale lo siguiente:
Disk /dev/mmcblk1: 16.1 GB, 16055795712 bytes
4 heads, 16 sectors/track, 489984 cylinders, total 31358976 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk identifier: 0x00000000
Device Boot Start End Blocks Id System
/dev/mmcblk1p1 16 27431871 13715928 83 Linux
/dev/mmcblk1p2 27431872 31350783 1959456 83 Linux
en tu caso supongo que si estará la partición 1, pero faltará la 2.
Con la orden n se crea una partición nueva, te pedirá el número (2) y el tipo (83) y donde empieza y acaba, para estos deja los valores por defecto que te sugiera el fdisk.
Después la escribes con la orden w, y finalmente te sales con q.
La puedes formatear con el propio linux con:
mkfs.ext3 /dev/mmcblk1p2
o dejar que lo haga el recovery, en cualquier caso debes volver al nvflash para reinstalar el recovery y quitar el boot del linux, hecho esto ya puedes volver a arrancar con el recovery y restaurar la versión que desees.
Seguro que hay una manera más fácil, pero si no la encuentras esto debería funcionar, aunque por razones obvias yo no lo he probado.