У меня точно такая же видеокарта (правда система 12.04). Неплохо работает экспериментальный драйвер из дополнительных драйверов.
Раньше на 10.04 хорошо работали проприетарные с офф. сайта.
Я думаю, твоя проблема в "Перепробовал уже кучу драйверов", дело в том, что драйвера из офф. сайта надо корректно удалять, в противном случае они оставляют "хвосты" в системе, которые не позволяют установить другой драйвер.
Что выдает команда?
cd /usr/share/ati
sudo sh ./fglrx-uninstall.sh
Если выдаст ошибку, посмотри что там в директории:
ls /usr/share/ati