Please give us more complete specs, CPU/RAM/MB and the make and model of the power supply.
For a game that can be that demanding a change of the core system might be the best way to go, but it depends on your useage, expectations and budget.
If you must stick with an AGP system (and God knows money is tight enough these days) go for the faster memory every time.
Fastest in class: HD3850. best choice: HD4650, it's newer tech and uses less power.
HD 3850 512mb GDDR3 is the way to go.
The 4650 wont perform as well even though it is a newer card, the 4670 is about the same as a 3850 performance wise but i dont know if thats out in AGP or not. (dont think it is)
@ mactronix: I have not seen the AGP HD4650 here in the UK but it is on the Newegg site.
@strangestranger: Yes, on both points.
@ GPotvin: As mactronix says, the HD3850 and HD4650 are about the same in performance, but the HD4650 uses less power, often an importaint point in older AGP systems with-usually-older and weaker power supplies.
It is really now up to you which way to go. A new card will give a nice boost but the game will always be limited by the CPU.