szerintem a TestDisk a te barátod (http://www.cgsecurity.org/wiki/TestDisk)
Ubuntunak pl a repóiban is benne van, használtam már DOS, cygwin, linux verzióit és teljesen rendben van.
Amúgy anno hasonló esettel sűrűn találkozam, Partition Magic és Windows XP párosítása az egyik XP patch után szétcseszte a partíciós táblát hasonló módon. A TestDisk-kel sok sört kerestem a koleszban akkor :)