I have an ATI HD4870 connected to a home cimema decoder, linked to a plasma screen.
After an ATI driver update: Win7 says "HDMI not plugged in" when the connected TV is off, even if the home cinema decoder is on. Everything worked fine before.
At some point, plugging out and back in the HDMI cable would fix it, then it stopped working too
Then I found the Windows+P key fix explained by Babbar here.
Just switch to single display, then back to extended mode.