Comme d'habitude, testdisk 
Cet outil te permet de refaire une table des partitions à partir du résultat d'un scan complet du disque. C'est un peu long, mais bigrement efficace.
Au passage, le paquet testdisk contient aussi photorec pour récupérer des fichiers après un rm ou un formatage "léger".
Si j'ai le courage (ou la prochaine fois que je l'utilise), je retesterais tout ça pour faire un tutoriel propre et précis. Je sais qu'il y a deux-trois trucs pas immédiats à faire pour que tout marche bien. En tout cas, testdisk m'a sauvé la vie deux fois déjà (la deuxième fois c'était plus par flemme de me battre avec fdisk mais bon, ça compte quand même
).