To add to kippy13's notes:
. A lot of PC133/100 memory chips will only report half their true density. If your motherboard uses PC100 RAM, return what you bought and ask for true PC100 modules. I am sure the package said it was PC100 compatible, but in many motherboards it is simply not. Be sure to do this soon, as PC100 is getting hard to find. Look at your original memory modules: what you want to buy in higher density is modules with chips on both sides of the circuit board rather than just one side.
. Memory slots themselves can be tricky. It might be, as kippy mentioned above, that you need to use slots #1 and #3, or some other variation. It might also be true that if slot #1 has 256, you need to populate #2 and #3 with ram densities no higher than 128 in order to reach 512 total.