I have almost the same video chipset (my GPU is a X1650 XT), though the video card is by MSI. I'm also on Linux, not Windows. At fullscreen and 1680x1050 resolution, my FPS on the menus varies (depending on the page displayed) between 60 and 30 FPS (as reported by the game after pressing '?'). This seems sufficient to me.
If you have remarkably worse values, this is most likely matter of your video drivers, which I think are somewhat outdated. Please read the hint on patched video drivers found on our FAQ at
http://faq.megaglest.org if you would like to investigate options to get more current video drivers which may work better with your current operating system version (which Windows version do you have there anyways?).