You can try a bios update, sometimes this fixes things up, but in general motherboards don't like working with two sticks of different size ram.
Is the new stick you bought at least the same speed as the first?
Just to be sure it is not faulty ram, try running with ONLY the new 512mb in your computer.