Jon,
I am wondering if your original RAM was CAS 2.2.2. and the new DIMM is CAS 3.3.3. It could be the BIOS is defaulting to CAS 2.2.2 with both sticks in the computer, thus making the CAS 3.3.3. stick fail.
You could try to manually set the CAS to 3.3.3 and see if it would boot with both sticks after manually setting the CAS Latency.
Take Care,
Richard
P.S. I still think your best bet is taking the new stick back and getting a 512Mb stick.