Did you at any point actually clear the BIOS (usually you have to shunt a jumper near the battery on the mobo)? When adding new RAM, especially of a different speed rating, some mobos get very picky when the old stuff is still installed - unless the CMOS is cleared completely. You might not need to get quite as drastic as your proposed solution - then again, maybe you will have to resort the the change, hopefully not.
Bookmarks