I had similar specs to you,
Amd 1900+ (1.6)
512 mb ram
geF4 Ti4200 64mb
and was getting low frame rates. I bought a 6600 gt and while it IS a great card I didn't get the improvment I expected, my frame rates only went up by 5/10 frames a sec. I then bought a new CPU so now I have,
Athlon 64 3200,
1 gig ram
GeForce 6600gt
and my frame rates are 70/80 frames pec sec at times and never below 50 online.
I would say CPU is the most important factor.