Just installed a Crucial 512 in my new laptop, and the system will not recognize it. I have tried both stick of memory in it separately, and they have worked fine. But they will not work together.

Any ideas?

Hello and welcome to techspot!
Are you sure they are the same speed? if not then maybe you should check every stick to have same specs in order to work correctly, even tough some memory will work togheter when they have different speed (at single channel and slowest speed of the both) some will not work or will cause further problems .
If you don't know the speed of your memory and the label don't mention it, try to download cpu-z and on the memory tab it will give you the specs you need, do that with every stick and match them. Good Luck!