The FPS you get will depend heavily on the game you play, on the resolution you play it at (how much does your monitor support anyway?), and on the graphic detail settings you choose.
Using DirectX11 vs DX10 or DX9 versions of the same game open up even more graphics options, which are usually GPU-heavy, but some rely quite a bit on the CPU too. The version of DirectX that you can use depends on your graphics card and your O.S. (maximum of DX9 on XP, for DX10 you need at least Vista, and only a few video cards have DX11 support).
High resolutions, FSAA, anisotropic filtering and some graphical effects depend mostly on the video card.
The amount of video RAM on the video card doesn't really _THAT_ much, there are several 512 MB videocards that thoroughly overperform a few 1 GB video cards. What REALLY matters is the GPU type.
High model detail, a few graphical effects, the game logic and physics depend mostly on the CPU.
Games that support physics acceleration do so on the GPU, but the physics-accelerated version looks different from the one without (more debris and such), you won't see a noticeable FPS difference.
CPU
Your machine has a Intel Pentium 4 631(3.0GHz) CPU, which is a single-core hyperthreaded processor. It's decent enough for older games and with older graphics cards, but for newer games and with a better video card, it's almost certainly a pretty nasty bottleneck.
The motherboard should be able to support most socket775 CPUs - some cheap but better-performing core 2 duo would be a good option, I'd say. Make sure you check though.
An Intel Core 2 Duo E7600 (3.06 GHz per core) should cost about 150$ or thereabouts, and more than double your overall CPU power.
Or you could go for a slower per-core clock but two cores, for probably under 100$, and it will still be a noticeable improvement in performance, because it's not just the clock, but the processor structure itself that's better. For instance, my junky Dual-Core @1.6 performs slightly better than my old P4@3.4. Core 2 Duo should be even better than that at the exact same clock speed. Depends on actual CPU though (cache and so on and so forth). You can check all of that on the intel home site (
http://ark.intel.com/Default.aspx ) once you look at a specific CPU.
VIDCARD
I assume you disabled the on-board video card when you put a new one in. And I assume you have a PCI-Express video card... what type of videocard is it anyway ? You can find out by running "dxdiag" and looking under graphics, or maybe you already know the exact model.
If you already have a reasonably-powered vidcard (although it's doubtful, not many decent ones had only 256 RAM), you might want to only upgrade your CPU instead.
You should be able to buy a Radeon HD 5750 (with 1 GB of RAM) for about 125$, which should work fine enough in a decent resolution and graphic detail on most relatively new games, although you might want to spend another 20-35$ and upgrade to a Radeon HD 5770. Or you could look for cheaper versions with only 512 RAM. Depends on your budget, I guess.
If you DO NOT care about DirectX 11 (and you probably don't) so DirectX 10 is enough, then the Radeon HD 4850 will also do relatively fine (slightly slower than the 5750), the 512 MB version you could probably find for only about 100$, the 1 GB version for about 110$.