Hey mate, I fixed it by installing Visual C++ 2012 runtime Update 3 (google them, it's the first result) redistributables, both x86 and x64 versions. I installed VC++ 2010 SP1 redistributables as well, both x86 and x64.
After doing this, I tried installing the Catalyst package provided by the laptop manufacturer, and this time it worked fine. I believe the official one from AMD driver page will work as well.
After installing Catalyst drivers, reboot and it should work now, check the context menu in desktop, 2 new graphic options should appear.
Try doing that and reply me if this worked or not. Good luck.