Der fglrx aus dem Catalyst 9.6 trägt die Versionsnummer 2.1.8673, was aber mit dem Kernel nichts zu tun hat. Allerdings war Ubuntu mal zu modern für die proprietären Treiber. Das sollte aber nicht mehr der Fall sein. Von der Kompatibilität könnte es helfen dann, wenn du eine ältere Version (8.04 mit LTS) oder z.B. Debian benutzt. Wobei das eigentlich schon länger nicht mehr das Problem ist.
Am besten, du guckst mal, ob du den fglrx überhaupt brauchst. Der radeon-Code soll teilweise sogar deutlich schneller sein als der fglrx-code. Auch wenn das lange nicht überall gilt.