It could be that your mobo is shutting you down because it feels that your new fan is not high enough rpms or else is not drawing enough current in the case that your old fan did not have rpm monitoring. This was a foolish implementation of thermal protection offered by some mobos in the past and you have no ability to change it - you are being shut down because the mobo thinks you are about to overheat because your fan isn't screaming along like the stock fan.
If you have an 80mm fan on your new cooler, it will produce these symptoms.
You can:
1 - go back to the old cooler
2 - go buy a 50ohm, 5W resistor and solder it across your new fan's two wires, causing the cpufan mobo port to give out higher total current, essentially faking out your mobo (a solution I used a year ago, see my post called "my motherboard is a retard")
3 - plug your old stock 60mm fan into the cpufan plug and your new fan into some other plug, so the mobo thinks the stock fan is being used. Put the 60mm fan somewhere else in the case. If you don't like its loudness you can trim off a portion of its blades to quiet it some.
4 - Do number 3 above and go into bios and turn off cpufan rpm monitoring. Then restart and throw away the 60mm fan. I would not count on the bios having this option though.
The quick way to test if this is the problem is to plug the old 60mm fan into the cpufan plug and start it up with the memory in.
The reason the system does not shut down when the memory is taken out is because the bios program never loads so your system's autoshutdown doesn't kick in.
Or it could be something else altogether...