testdisk acabou funcionando. A questão era que o fdisk inicia partições no primeiro cabeçalho e setor em um cilindro. Qualquer ferramenta que possa iniciar em um deslocamento arbitrário também deve funcionar.
Uma tabela de partição confusa não é perda de dados.