underclocking helped you? my *wild* guess is that maybe yer having a voltage issue. can you check in the bios to see what voltage is being supplied and then check your cpu specs to see what voltage it requires? also check the memory specs. for example, you wouldn't wanna run pc100 on a pc133 bus...
also, did you buy your cpu retail or oem? if oem, i'd find some way to make ABSOLUTELY certain you didn't get a remarked chip (a 900mhz chip "remarked" and sold as if it were a 1ghz for example).