Check the md5 of the ISO file you used to burn the CD. If it fails then download it and check it again (try another mirror).
If that passes, run an md5 check on the CD itself (there is an md5sum.txt file right on the CD). If that fails, toss it and burn another one.
As a final test, boot the CD and when you get the the first splash screen with the count down, hit ESCape and run the disc check from there. If the md5sum check passes but this test fails, you've got some kind of read compatibility issue between the computer that burned the disc and the one trying to boot it. Not a likely occurrence, but if it happens then you should try a different burner and/or media (or preferably burn it in the computer that will be booting & installing from it)..
If all tests pass then it is a problem with the hardware, or some severe compatibility issue. Run the memory test from the CD and let it loop for a while. FYI: Just because Winblows can format a HDD it doesn't mean there's no problem. Windows doesn't do much error checking during a format, especially if you did a quick format. Many HDD makers have free diagnostic utilities you can get from their support sites to properly test the drive.