A more reliable way to format the disk is to download a Linux live CD, boot from that and format the drive while it isn't mounted. The Windows format utility sometimes likes to do strange things with the flags and sizing in the partition table. If you're only going to install Windows again and aren't likely to bother with partitioning then the Windows utility will do fine, just make sure you format the disk and not just install over the top of the existing Windows installation.