Here's what sounds like is happening:
You put in some incompatible ram. Maybe it's high-density, I dunno, but it's only seeing half of the chip, i.e. only 256MB of ram. Now, 512MB plus 256MB is 768MB, so we still have another 8MB of ram missing. Easy answer, that PC most likely has integrated graphics, and 8MB is a pretty standard amount of ram for integrated graphics to use. So, that 8MB is used for graphics and is seen as graphics ram, not system ram. So, the amount of ram that will show up will be lowered by 8MB. So, if you put in a separate graphics card, you'd most likely see the "full" 768MB of ram.
If you want to troubleshoot this further, you could try swapping the sticks of ram, if that doesn't help then try taking one stick out completely? Does it show 512MB of ram (or rather, 504MB due to the 8MB taken for graphics)? If it does, try with the other stick of ram. If you see over 500MB of ram available each time, then it must be a problem with having both sticks of ram present at the same time. If you notice that with one stick it only shows 256MB (or 248MB), then that's definitely the problem ram.