I tried all the steps but wasn't able to get it working.
I have 2 HD4870x2 in crossfire configuration. After digging a little more I found a thread on Guru3D which suggested that CCC v11.10 are compatible with Win8.
Here is the steps I followed
1. Uninstall the existing AMD driver by following steps 1-3 that NlTESHADE suggested.
3. Download and install 11.10 ccc package (it is available from multiple sites. make sure you download from a reliable source.)
You MUST reboot again to be able to enable CrossfireX
I hope this helps