|From what I have heard they are lame.|
If you are using Windows7 then 1GB is minimum but 2 is really needed, if you are using XP then 500MG is minimum bit 1GB is really needed BUT that would have nothing to do with damaging a CPU. In fact just about the only way to damage a CPU these days is to overvolt them. This would mean an incorrect BIOS setting or a runaway power supply. Since the new motherboard would have had a new BIOS that was not tampered with (unless you are overclocking and not doing it correctly) plus the fact that original Gateway motherboards would not have the voltage adjustable, it was not BIOS settings. This means that either your old CPU is still good and your problems will return, or your power supply is bad and you may still have trouble again. You can send the CPU back to the factory or Gateway and they can test it for you, if it went bad they can verify this and why (too much voltage is definitely detectible by the factory) and may be warrantied if bad for other reasons.
You have to be a little bit crazy to keep you from going insane.