If you haven't come across the term before, the handshake is what happens when two or more devices in a HDMI chain talk to each other. This happens between two devices when at least one is powered up. It's the reason why the HDMI cable carries 5 volts. The voltage carries over to the unpowered side of the HDMI connection, and it allows the HDMI chip to wake up and communicate with the device on the other end of the HDMI cable.
The handshake provides information about the capabilities of each device so that a common set of compatibilities can be established. For example, you might have a whole bunch of audio formats enabled for sound over HDMI from a console, but it's connected to a TV that can handle digital stereo (2ch PCM) and Dolby Digital up to 5.1. The handshake will establish the common ground so that the console doesn't send the audio formats that the TV can't understand. The handshake also tests whether the encryption is in place to allow digitally secured content to be played. In other words, the anti-copy protection.
Handshaking happens at start-up, and when there's an input change, and when there's a break in the continuity of the source signal such as a resolution or refresh rate change. There are also times when the handshake polls, so it is continuously tested. Any of these can cause a TV to flag up its HDMI input label. These are all the things that are in-spec. There are also things that can be out of spec or on the borderline.
HDMI has allowed us to have a simple connection that does a lot. It has become universal much in the same way that SCART did thirty years ago. That wasn't a perfect connector, but it allowed us to move standards forward. HDMI is in the same position; not perfect, but it enables progress. In making that progress, we, the AV users and enthusiasts and professionals sometimes take things for granted. You'll have probably heard the often-parroted "It's digital. It either works or it doesn't" line. That's one of the things we take for granted, but it obscures a more complex truth with a facade of a convenient appearance.
The XBox in its various guises is known to have HDMI handshake issues. PCs are also notorious for being difficult to interface by HDMI. If you're still having problems then the next course of action is to isolate whether it's just one source or both. After that, you might want to take a look at the various HDMI EDID Managers. These are little boxes that sit inline with a HDMI connection between a source and a display. They are used to emulate a consistent set of display characteristics. This acts as an insulating layer between the source and a display. Maybe have a look on Amazon. There are ones there for under £20 and they're simple to set up with a single rotary dial to select a display profile.
