It's likely not the CD, more likely to be a wonky setting in the BIOS that's preventing the CD from booting. Check that CD boot is enabled and placed in a preference before your hard disk. Try booting without your hard disk installed too. If it does boot without it, you may want to format the disk again.
Just as a check, though - you are downloading an ISO of linux and then properly burning the image to a disk using a utility that can do it (such as Nero)? Or are you simply burning a data disk that contains the ISO file?