Comment 16 for bug 1068739

I think this is due to some paths missing in the fglrx package for amd64 architectures.

A workaround is using the fglrx-* packages from my PPA:
https://launchpad.net/~andrikos/+archive/ppa

Could you please give it a try and let me know if they fix your issue?