Du hast fglrx aus den Ubuntu-Repositories installiert, also nicht mit dem Installer von der ATi-/AMD-Seite oder sonsteinem Repository? Wenn ja, poste mal die Version sowie die deines Kernels.
Hast du passende fglrx-Kernel-Module installiert und werden die richtig geladen? Wenn du nur Sourcen hast dafür, solltest du (als einfachstes) module-assistant mit allen empfohlenen Paketen installieren, die Sourcen entpacken und m-a prepare, dann m-a a-i fglrx ausführen.
Außerdem hat fglrx eine Abhängigkeit gegenüber libstdc++5. Schau mal, ob das Paket installiert ist.

Und ansonsten das übliche, xorg.conf und Xorg.[n].log (nicht nur den Ausschnitt), bitte.