I'm thinking the drive might be faulty. Format programs don't usually screw up unless there's something wrong with the drive.
Either use a linux box to blank the drive (command is "dd if=/dev/zero of=/dev/hd#, where # is the linux letter of the drive (does not necessarily match windows' letter)) or use some utility that does the same thing (the Ultimate Boot CD would probably do it).
Then try reformatting it.
If it succeeds, the problem was probably hidden deep in the filesystem structure and the blanking fixed it.
If it does not, you've got yourself a couple of magnets.

Edit: if you don't have a linux equipped computer handy, DamnSmallLinux starts from the cd, is only a 50mb download and would do the job just fine without even requiring the removal of the disk from the laptop.