Digital is never really digital in reality except on a logical level, particularly when dealing with very high-speed signalling. It's not unheard of for cable signalling to actually use multiple voltage levels, Gbit ethernet does that I believe, not sure about hdmi. In any case, noise/interference, cable impedance and so on is definitely a factor at the multi-Gbps speeds HDMI works at, more so if you have a long or cheap cable with poor shielding. When you start going even faster, like with thunderbolt, you even need active transcievers in the cable itself to compensate for the limitations of copper conductors. If the receiver can't distinguish reliably between the various signalling levels you will get errors in the transmitted data of course, even though it's digital data being transmitted...This is most peculiar and contradicts everything I know about HDMI. HDMI is supposedly 100% digital and shouldn't ever suffer the type of signal degradation issues common to analogue cables.
I'm surprised a cable included with the system would be causing problems though, that's really strange. Manufacturing defect perhaps, or maybe a seating issue which replugging would have solved...?