Hast du zu dem neuen fglrx-Treiber (also dem proprietären von AMD selbst) ein passendes Kernelmodul kompiliert? Wenn nicht, könnte das eine Fehlerquelle sein.
Der von Knumon verlinkte Beitrag ist dabei gar nicht so~ spezifisch für Ubuntu. Das meiste lässt sich leicht abgewandelt auf andere Debian-basierte Distros ummünzen.

Der radeon-Treiber (bzw: radeonhd bei X1xxx und den HD-Modellen) wären Alternativen dazu und dürften grundlegende 3D-Beschleunigung bieten. Beide sind Open Source und dürften bei deiner Distro mit dem X Window System mit installiert sein. Oder müssten sich leicht nachinstallieren lassen.
Der Fehler könnte aber auch schlichtweg in der xorg.conf liegen. Du findest sie meistens im Verzeichnis /etc/X11. Wär am besten, wenn du die Datei posten würdest.