I'd make a guess and say you're upgrading to a larger drive. If it's to a 12Gb+ drive, it may be because the BIOS doesn't support Int13 extensions/LBA, in which case try using "FDISK /X" and creating two or more partitions of less than 8Gb each.
If it's for a 40Gb+ drive, then answering YES to large disk support enables FAT-32 for drives above 32Gb, but, as above, both the OS and the BIOS have to support it. In which case say NO and make 2 or more partitions of about 20Gb.
Lastly, in case it's just a problem with the verification check, try using, "FDISK /ACTOK", which makes FDISK skip the disk integrity check altogether. If it works, use scandisk to check the disk after you format it.