Argh!!! I JUST got a new TV, a Samsung LN-T5271 and am trying to hook up my Vista MC to it using a DVI->HDMI cable, and suddenly I'm finding that I have the exact same problem described. Ugh.
Basically, everything works great if I boot the PC while the TV is on. If I turn the TV off and then back on, I get a blank screen and a "Weak or no signal" error. Everything is fine I then unplug and re-plug the DVI from the back of the PC.
ATI Radeon 9500 Pro, Vista Home Premium, Newest (v7.10) Catalyst drivers.
Couldn't seem to find any solution or settings in either the graphic card drivers or the TV that help it out, and started searching the web, ran across this post.
Might be time for a full-blown HTPC upgrade, maybe go the pre-built cablecard route.