Tienes que apañarte con los drivers libres que ya trae Ubuntu o con las ultimas versiones del libre por PPA. Tu tarjeta está completamente soportada por los libres.
Tu gráfica ya ATI/AMD la abandonó de sus drivers hace tiempo, olvídate de los catalyst.
Creo que los actuales Catalyst para linux solo soportan las RadeonHD 2xxx y superiores, y en Windows solo las series RadeonHD 5xxx/6xxx/7xxx (las RadeonHD anteriores ya están en los drivers "Legacy" a merced del tiempo y con los fallos que les salgan sin solución, y cuando no funcionen no funcionaran)