I also have a similar problem...I have a Dell 17 inch flat monitor but connected by a KVM box to 2 PCs, one the original Dell and the other my old hybrid. If the switch box is not set to the booting PC I get the "Cannot Display This Video Mode" on the old one and the Dell seems to select a different screen resolution or something (the font looks bigger). Not a great problem, just have to wait while they boot individually.

Hmmm.....