Good to have 256MB, but the GPU itself is still not all that speedy. I'm not sure whether the one you have supports DirectX 8.1 or 9.0 (they made them both ways), but that can make some difference, too.
If you're not sure that the bottleneck is the graphics card, here's a good test. Check your framerate in a few different places, which range from quiet to moderately busy. Now get into your game video settings, and drop the draw distance and shader effects significantly. Repeat the test with the new graphics settings. If your framerate went up, the bottleneck is probably your graphics card. You can either enjoy your game with the new settings and higher framerate, or upgrade to a faster card and get a little more detailed graphics without becoming lagged.
I'm assuming that your BIOS is set to support 8x AGP, that you have a recent version of your graphics card's driver, and have DirectX 9.0 installed. If not, you might try fixing those things, they are all free and likely to make a measurable difference in framerate.