I had the same problem with a box from a friend of mine. I speculated it was the metadata from previous installations the culprit, I cleaned the hd and then installed again and the problem was gone.
Google for 'man shred' and 'man wipe' . Grml and Puppy Linux have those programs, make sure you clean it, partition by partition and not the whole disk.
i.e.
# shred -fuvz /dev/sda1
and so forth, after the first partition is cleaned, continue with the next (including the partition where swap is), /dev/sda2, /dev/sda3... 'shred' will destroy crud 3 times and on the fourth it will add zeroes to the partition.