I have yet to see their uninstaller script do anything but break Mesa and possibly stop X from loading because it didn't remove part of the Catalyst bundle.
Their official installer is nasty shit, seriously. Don't use it.

(OK, it is your system, but don't say nobody warned you.) If you feel comfortable poking around figuring out why X won't load, use their installer. If you want it packaged in a semi-sane manner that probably won't destroy your system* use the distribution specific packages.
(*This isn't to say that FGLRX won't randomly lock up your system forcing you to hold in the power button, but that's on a bad month, like this month's 11.9 release. Usually.)