sfdisk
deve ser capaz de "corrigir" este problema facilmente; algo assim deveria "funcionar":
sfdisk /dev/sda -i -c 1 07
No entanto, é possível que, além do tipo de partição que está sendo alterado, as posições de partição (início, fim) também estejam corrompidas. O TestDisk deve detectar esses problemas e escrever uma nova tabela de partições um pouco apropriada.
O problema é que, considerando que a tabela de partição estava corrompida, é possível, não, que os dados também sejam.