a similar thing happened to a friend. turned out to be a grounding issue and was a very common problem with his TV model (a Westinghouse). I think he had to constantly plug and unplug the HDMI cable from the TV (leaving the 360 end plugged into the 360) and plug it back in to get it to eventually work. He thought it was one port but once he switched to another HDMI port, it started happening there. He thought it was a 360 problem but that's because he mainly uses the 360. When he started using other devices in those ports (BluRay player, etc.), it would start to happen to them too.
In the end, he couldn't return the TV (Black Friday deal). The TV was otherwise great. So he ended up getting a component cable and forgetting about it.