The latest upstream code (Linux 3.0 + Mesa 7.11) is noticeably faster for Nexuiz at the tested resolutions than what is found in Ubuntu 11.04 (Linux 2.6.38 + Mesa 7.10). The frame-rate goes up on average by 41%. A larger improvement though is found when disabling Swapbufferswait and enabling the R700 class color tiling via the xorg.conf. Adjusting these two non-stock options takes the frame-rate up by another 76%, or a performance increase of 2.49x of what is found by default in Ubuntu 11.04. Interestingly, there seems to be a sync/swap problem with these options at 1920 x 1080 that is pushing its frame-rate down to 30 FPS in this case. However, still, the proprietary Catalyst driver remains much faster.
With the OpenArena game there isn't a huge performance boost out of moving to Linux 3.0 / Mesa 7.11 for this high-end Radeon HD 4000 series graphics card on R600g. Oddly, due to some syncing issue, the 1920 x 1080 frame-rate actually is higher than 1024 x 768 and 1280 x 1024 with this stock configuration. There still is, however, an 80% increase in frame-rate when disabling swap buffer waiting and enabling color tiling.
The Catalyst driver still reigns supreme in the World of Padman game, but at least the two driver tweaks will squeeze some extra frames out of the system so it is a playable experience at 1920 x 1080 for the Radeon HD 4870.