I'm running a 3500+ with an X1900XT, upgraded from a 7800GTX 256mb, and can notice the difference.
Keep in mind that I run games at 1200x1920 or 1050x1680 because I won't go any lower. But at either rez, I get a 20-50% increase in framerate. At lower resolutions, the need for a high-end card decreases.
With the X1900XT and the Chuck patch, I can also run Oblivion with HDR and 4xAA. My test run was only about 5fps lower than without 4xAA.
The 3500+ might be a bottleneck -- I can't say for sure, since I haven't tested it against any other CPU -- but you can't go wrong with a high-end, single-card GPU from either nVidia or AT paired with the 3500+. From what I've read, significant bottlenecks occur only with 2-card, high-end GPU solutions. You'll still get a performance increase with any 2 GPU's, but the bang-for-your-buck factor decreases severely without a high-end CPU.