I just noticed something today that may help some of you.
The drivers I downloaded directly from my laptop manufacturer (HP) earlier in the week fixed my HDMI issues. However, today in the Catalyst Control Center, I clicked the option to enable 10-bit pixel format support. In Windows 8.1 I had no issue when turning this option on. When I turned it on today however, my laptop > HDMI > TV connection would no longer work. I had the same issues I had prior to installing the drivers from HP.
I disabled the option and now the HDMI connection works again.
Now that I think back, I think this may have been my issue all along. And this may be the issue some of you are having as well.
Make sure the 10-bit pixel format support is not enabled. You have to restart your computer after disabling it.