Desafio, você tentou refazer o rótulo no disco (clique com o botão direito do mouse no novo registro mestre de inicialização) e depois particionou em um alinhamento 4k? Lembro-me de que o parted estava fazendo algo estranho naquela época e, se não atingisse o alinhamento, ele quebraria. Também pode ser o caso em que, em unidades antigas, uma das seções importantes do disco onde a partição contém metadados pode ter um setor defeituoso. Uma maneira de verificar seria usar ctrl + alt + F2, depois de iniciar o formato, entrar no console e digitar dmesg e ver se ele reclama de setores defeituosos. Em caso afirmativo, o disco é ruim. Procure algo parecido com:
[Sun Jul 21 13:36:32 2013] ata4.00: exception Emask 0x0 SAct 0x1 SErr 0x0 action 0x0
[Sun Jul 21 13:36:32 2013] ata4.00: irq_stat 0x40000008
[Sun Jul 21 13:36:32 2013] ata4.00: failed command: READ FPDMA QUEUED
[Sun Jul 21 13:36:32 2013] ata4.00: cmd 60/20:00:2c:eb:7e/00:00:08:00:00/40 tag 0 ncq 16384 in
[Sun Jul 21 13:36:32 2013] res 41/40:00:2f:eb:7e/00:00:08:00:00/40 Emask 0x409 (media error) <F>
[Sun Jul 21 13:36:32 2013] ata4.00: status: { DRDY ERR }
[Sun Jul 21 13:36:32 2013] ata4.00: error: { UNC }