From your post of what you already have, am I correct in saying this is what you need?
-mobo
-cpu
-psu
-video card
-memory
-hdd
-optical
If so, this is along the lines of what i'm thinking:
-mobo: $60
-cpu: $60-$80 AMD dual or triple-core
-psu: $50
-video card: $182-222
-memory: $50-$70, 2GB or 3GB total
-hdd: $40
-optical: $18
It would be nice to be able to eke 4GB of memory out of the $500, but I don't see how it's possible without sacrificing too much in the video card area. It's absolutely painful to put down 2GB of memory for a gaming machine, so maybe 3GB should be your minimum there, and that should do alright. A good quality psu shouldn't be difficult to find for around $50, and neither should a basic mobo (without tons of features), that works just fine.
Of course, this price list is going off getting everything at newegg. Things would change if you went to places like ebay or craigslist for some of your items, even say a local store selling a cheap used dvd rom drive, etc.
As things stand right now, I wouldn't be too worried about going with a dual-core processor for gaming, although a nice cheap tri-core would be preferred of course. Obviously you should go with AMD due to your price point.