Olá,
Ainda usando como exemplo o computador com a placa de vídeo da Nvidia, quando eu vou em "Sistema -> Administração -> Drivers de Hardware", o sistema me dá várias opções de driver, dentre elas uma que vem marcada como (recomendado). Se isso também acontece no seu caso, tente todas as outras opções e veja se o mesmo ocorre.
Se não funcionar, talvez de onde você baixe o driver haja outras versões disponíveis. O ideal é que você tente o máximo de versões possíveis. Se nenhuma funcionar, talvez seja uma boa ideia você postar esse "bug" no no site da ATI.
Eu sei como é ficar sem aceleração 3D, já que tive um laptop com chipset da amaldiçoada VIA e tenho um desktop baseado no chipset da porcaria da SiS. Isso é realmente muito ruim, mas o pior é quando acontece com um equipamento baseado num chipset que aparentemente é bem suportado pelo Linux, como é o caso da AMD.
Bem, o importante é que parece claro que o problema é o driver de vídeo da ATI. Daqui em diante, só posso lhe desejar boa sorte e aconselhar a você que continue buscando, principalmente no Google. Há alguma probabilidade de alguém já ter passado pelo mesmo problema e resolvido.
Abraço.