I had the same issue just after putting in a new AMD 7850 (Win7 64-bit).
Some combination of the following worked:
Install DirectX 9.0c
Uninstall everything Catalyst related
Reinstall Catalyst, but only install the graphics driver, none of the extra stuff
Run with -nopatchui command line switch
That got past the installer, but got stuck on a black screen with only a cursor. Running again without -nopatchui gave me a normal login prompt.