I have the same problem with my newly built midtower. I did a google wide search, and read from some forum that the individual did a super clean uninstall just
like you. But when reinstalling it was a 2 step procedure :
1). Install from its own pkg the chipset drivers only (can be found on the AMD website drivers pg ). Then reboot system.
2). Then install video drivers from Radeon Adrenalin software pg for your specific graphics card.