You'd be surprised.
In March of '09 I built my rig for $350. You would have to add the cost of a disc drive and a power supply, so I'd say my rig would cost $450 with those.
I play on high / ultra settings in Cata (beta) EXCEPT for shadows (good, any other setting above that caused odd things in the beta) and EXCEPT for Anti Aliasing, at 1600x1200 resolution. So, basically, high settings at a common resolution range.
I average around 70 FPS, 150+ inside buildings, 40ish during 10 man raids, 25ish during 25 man raids.
Another year past, and you can get newer components for around the same price. I'd say you could EASILY average 50 FPS in a raid with $500. The following list is the order in which you should buy the parts, for compatibility's sake.
Throw in an AMD dual core processor and a compatible motherboard. Important things to look for are PCIe 16x (I think the highest interface is 3.0 or something, but you don't NEED that!), and a 1333 bus speed or higher, supporting DDR3 RAM. All of that info is easily found on the part's spec sheet. I prefer ATX mid sized boards, but that can be a large rig.
Add 2 sticks of 2GB RAM, 1333 or faster.
For a baseline, start with an Nvidia 9800GT or ATI equivalent. You can go higher, but the 9800 is still a GREAT card and can be found for dirt cheap.
Put around a 500GB HDD (7200 RPM SATA), more if you store a ton of music or videos, or play a LOT of games.
You'll need a case and a power supply. Get the case to match the motherboard, and at least a 500w power supply. The faster the computer, the more juice it needs, and the worst feeling is starting up WoW to hear the good ol' pop from your power supply. Been there, done that.
Get fans for the case. Cases tend to come with a single fan, but have the space for more. My case has an HDD fan at the front, a side fan, a top fan, and three rear fans. I never got around to buying the HDD fan, and there's one empty rear fan slot, meaning I have 3 fans. This is adequate (exhaust top and rear, intake side btw) to keep the computer around 50*c while gaming. Again, more powerful components require more cooling.
If you use discs still, a DVD drive will be one of the least expensive things you buy.
You could also throw in a nice Sound Blaster audio card if you have a good speaker system. I use a 10 year old Sound Blaster Audigy to this very day, works great for 5.1.