Tive o mesmo problema após atualizar para o Windows 8.1. Meu monitor HDMI ASUS de repente tinha a borda preta e fontes difusas. Meu segundo monitor, conectado pela velha escola VGA, estava funcionando muito bem. E assim como sua descrição, instalar o Catalyst Control Center não funcionou (nenhum executável, o driver era o AMD Radeon HD 7500 Series).
Depois de muita pesquisa, ficou claro que eu tinha que definir o valor de overscan (underscan) para zero, mas sem acesso ao Catalyst Control Center, eu tinha que entrar no Registro. De AMD Catalyst 12.6 lançado (+ 12,7 Beta) , eu mudei o registro e reiniciei e o problema foi resolvido :
I've seen that on one of my computers that's connect to a monitor that only has HDMI input. Set it right and it would revert after reboot or from hibernating. I found a fix somewhere by googling sometime back.
Go to the following key in the registry:
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Contro l\video{####....}%bl0ck_qu0te%00
Create a new DWORD:
"DigitalHDTVDefaultUnderscan" = dword 0x0000
Note: there might be several {####....} , should be the one with most of the ATI settings.