Creo que Partition Magic no es una mala alternativa.
Ojo que linux instala en este orden MBR->Sector Arranque->Part. Swap->Part. Ext2
con fdisk no podras borrar la particion Ext2, pero Part. Magic efectua eliminaciones seguras y deja el disco en estado NO Asignado, eso quiere decir que con Fdisk podrias crear una particion Primaria....una vez creada esta particion instalale Win95 o Win98 (no XP) para que vuelva a leer el sector de arranque y la MBR.
al menos así he solucionado yo este tipo de problemas....suerte !!