Eu poderia recuperar todos os dados usando o utilitário testdisk
de um live CD do Ubuntu!
Parece que o Windows danificou o MBR do HDD e usando este programa eu poderia inspecionar o conteúdo real do HDD e então reescrever o MBR sem problemas e recuperar toda a partição.
Para instalá-lo, basta fazer um sudo apt-get install testdisk