Sei froh dass PartitionMagic nichts macht, Du würdest vermutlich Deine Daten verlieren. Die Platte muss fehlerfrei sein, damit Du mit Partition Magic Deine Windows-Partition verkleinern kannst. Du kannst Dich auch nicht unbedingt auf eine vermeintlich gelungene Clusterreparatur verlassen. Partition verkleinern ohne volles Backup macht man sowie so eigentlich nicht.
Du wirst erstmal Deine Daten, Deine Windows-Installation auf eine andere Festplatte sichern müssen, definitiv, leider. Bei Clusterfehlern werden Tools wie DriveImage nicht arbeiten. In so einem Fall hat sich Microsoft-Backup bewährt, auch wenn es eine Neuinstallation von Windows verlangt, meist plus Monitor-inf-Datei, Grafikkartentreiber und ev. Festplatten- und Mainboardtreiber. MS-Backup musst Du ev. von der Windws-CD nachinstallieren. Später kannst Du das MS-Backup einspielen, also Programme, Windows-Einstellungen (und sonstige, eben die Registry) und Daten werden dann installiert.
Wenn Deine Daten und Programme gesichert sind, kannst Du versuchen die Festplatte mit einem Tool von der Homepage des Festplattenherstellers zu reparieren. Alle Partitionen löschen. Außerdem Killmbr und Nullen schreiben (sogenanntes Low-Level-Format). Am besten mal auf ext2 formatieren (SuSE-Linux-CD ausleihen, es geht auch eine die 2-3 Jahre alt ist, Yast 1 oder 2 benutzen) und den Problembereich auf FAT16 umformatieren. Immer zwischendurch Festplattenerkennung im Bios und Killmbr. Wenn Du die Platte nicht fehlerfrei bekommst, kannst Du vielleicht noch Garantie anmelden (meist 3 Jahre). Aber dann würde ich da nichts mehr draufspielen.
http://www.heise.de/ct/ftp/result.xhtml?url=/ct/ftp/ctsi.shtml&words=killmbr