Ich würd die bei 'ner neuen Platte auch raten, sie umzutauschen.
Bei einer bereits gebrauchten Platte einfach eine Linux-Live-CD reinwerfen, booten, die HDD zB als ext3 formatieren und unter Windows "normal" als NTFS. Manchmal hängen einfach ein paar Bits quer und Windows stößt beim Formatieren an seine Grenzen...