Você precisa usar os drivers de código aberto que não são tão rápidos quanto os da ATI. Como a ATI não suporta mais o seu cartão no Linux, não há muito o que fazer.
Extraído de wiki.cchtml.com:
Radeon (Catalyst Legacy & Open Source)
A ATI / AMD desativou o suporte a Catalyst para esses cartões no Catalyst 9-4. Estas placas são suportadas com o legado ATI 9-3 Catalyst, mas você DEVE usar um kernel 2.6.28 (ou anterior) e Xserver 1.5 (ou anterior). Por exemplo, você pode usar o Catalyst 9-3 se estiver executando o Ubuntu 8.04 ou o Debian Lenny / 5.0. O suporte a código aberto é bom e o 3D ainda está melhorando.
- RV530 / RV560 Radeon X1600 / X1650 / X1700, M56, M66
Executar seus jogos com o compiz disable (ou usar o Ubuntu2D em vez do desktop padrão do Ubuntu) ajudará, mas não muito.
Pense que isso é tudo que você pode tentar.