Por supuesto, que estamos hablando en casos donde solo se trata de la destrucción de la tabla de particiones, pero no del formateo de las mismas, en este último caso es prácticamente imposible recuperar los datos.
Cuando se trata de la corrupción de la tabla de particiones, existe una herramienta llamada Gpart. Este mágico software hace un escaneo del disco duro y encuentra las particiones por sí mismo sin necesidad de la tabla de particiones, y de paso, lo repara, sí, leyeron bien, vuelve a dejar todo como estaba antes del desastre.

Instrucciones
1) Ingresar con Knoppix
2) Usando Gpart para detectar particiones, lo que puede durar mucho tiempo depende el disco y las particiones (lo he probado en un disco de 20 GB y cuatro particiones, demorando unos 40 minutos aproximadamente)
[root@knoppix root]# gpart /dev/hda
Begin scan...
Possible partition(DOS FAT), size(3999mb), offset(0mb)
Possible extended partition at offset(4000mb)
Possible partition(Windows NTFS), size(3999mb), offset(4000mb)
Possible partition(Linux ext2), size(3072mb), offset(8000mb)
Possible partition(Linux ext2), size(3072mb), offset(11072mb)
Possible partition(Linux ext2), size(3072mb), offset(14144mb)
Possible partition(Linux ext2), size(2353mb), offset(17216mb)
End scan.
Checking partitions...
Partition(DOS or Windows 95 with 32 bit FAT): primary
Partition(OS/2 HPFS, NTFS, QNX or Advanced UNIX): logical
Partition(Linux ext2 filesystem): logical
Partition(Linux ext2 filesystem): logical
Partition(Linux ext2 filesystem): primary
Partition(Linux ext2 filesystem): primary
Ok.
Guessed primary partition table:
Primary partition(1)
type: 011(0x0B)(DOS or Windows 95 with 32 bit FAT)
size: 3999mb #s(8191953) s(63-8192015)
chs: (0/1/1)-(1023/15/63)d (0/1/1)-(8126/15/63)r
Primary partition(2)
type: 005(0x05)(Extended DOS)
size: 10144mb #s(20775888) s(8192016-28967903)
chs: (1023/15/63)-(1023/15/63)d (8127/0/1)-(28737/15/63)r
Primary partition(3)
type: 131(0x83)(Linux ext2 filesystem)
size: 3072mb #s(6291456) s(28967904-35259359)
chs: (1023/15/63)-(1023/15/63)d (28738/0/1)-(34979/8/24)r
Primary partition(4)
type: 131(0x83)(Linux ext2 filesystem)
size: 2353mb #s(4819248) s(35259840-40079087)
chs: (1023/15/63)-(1023/15/63)d (34980/0/1)-(39760/15/63)r
3) Usando Gpart para reparar la tabla de particiones:
gpart -W /dev/hda /dev/hda
4) Listo, ahora solo resta reiniciar la PC y todo volverá a la normalidad.