I had this problem last night... Came out of nowhere -- I was watching TV, when the time came to put the kid to bed. So I ask the DVR to record the rest of the movie, turn off the TV and go upstairs.
A few hours later I turn the TV on again and boom... This message. Fortunately, FiOS rep was able to "refresh" the box remotely after I complained via an online chat. Unfortunately, they aren't available 24x7... What he told me was that I could've done the same reset by disconnecting both the power and coax cables into the affected STB. I only tried the power cable myself.
One other datapoint is this -- this DVR is new: a slick black one, that replaced the old-style grey (which went bad) several weeks ago. It worked fine until I changed the video-output setting from 720p to 1080i (the highest supported) yesterday morning. It worked fine with that too for several hours, but, I'm guessing, maybe, the outputting at the higher setting may be taxing enough to increase the danger of HDCP miscommunication? Still, that's hardly a valid excuse to disable HDMI from that point on without manual intervention...
But, the point is, when you suddenly see this message after things worked fine for a while, there is nothing wrong with your equipment. There is nothing wrong with the STB's hardware either, apparently. The HDCP-implementation is just being the аsshоle it was designed to be, I fear. Contact the company and make them deal with it. When they get tired of it, they'll ask the manufacturers to relax the implementation.