Running Nexuiz (with high quality settings) on the "R300c" classic Mesa driver as used by default up until Ubuntu 10.10 is pretty much garbage for an ATI R500 GPU. The ATI Gallium3D driver is much faster and handles the game properly, but the performance is still too low -- even at 800 x 600 -- to be playable. As the hardware is very limited and the game demanding, the recent open-source ATI driver improvements do not do much good here for a Mobility Radeon X1400.
When upping the resolution to 1400 x 1050, which is the ThinkPad's native panel resolution, the story is the same. Unfortunately, the Catalyst 8.10 driver had not worked for Nexuiz in this configuration.