The problem is that the game runs no faster than 0.5 fps.
Here are the specs.
P4 1.6
512 MB of SDRAM
ATI Radeon 9600
I have installed the official video drivers form ATI's website. So what could be the problem. Is there any test I can run to test opengl performance on my machine?

check if glxinfo or fgl_glxinfo says something about direct rendering.

if it mentions mesa remove any mesa related packages and possibly reinstall driver

Ok. Here is the output.
qwe@kubuntu:~/bin$ glxinfo | grep direct
direct rendering: No
OpenGL renderer string: Mesa GLX Indirect
Which mesa packages do I remove?

libgl1-mesa-dri
libgl1-mesa-glx
libgl1-mesa-swrast
libgl1-mesa-swx11
libgl1-mesa-swx11-dbg
libgl1-mesa

those don't all have to be installed though

I can't delete these because xorg and bunch of packeges are tied up to it. How do I delete them without deleting dependencies?

then ... follow these totally great guides. Although they say that the package manager is supposed to take care of mesa automatically

http://wiki.cchtml.com/index.php/Ubuntu

You do not want to remove mesa. That would be bad, as mesa provides software methods for extensions that you can't do in hardware. But you do want to make sure that you have the 3D drivers for your card installed over mesa....

that's only if the driver is built on top of mesa. which the fglrx drivers aren't.