Does this happen when you (1) purge as I suggested (2) install fglrx via apt-get?
If so, what happens when you (1) purge fglrx as I suggest and (2) install fglrx-updates via apt-get?
Both os these will attempt to install the driver and also install Catalyst. It would be nice to know if the problem is related only to fglrx, or if it also applies to fglrx-updates.
Please, let us know if you have tried these and then what any error messages were.