I've seen this sort of inconsistency in a couple of cases:
- Plug-in video cards -- These sometimes don't support the monitor's optimum resolution, particularly when using a card intended for BIOS-based computers on an EFI-based machine. In this case, unplugging the video card and using the motherboard's native video output may work better. Switching to an EFI-enabled card (or upgrading the card's firmware, if such an upgrade is available) may help, too.
- Enabling/disabling the CSM -- The Compatibility Support Module (CSM) is an EFI feature that enables the computer to boot BIOS-mode OSes. Sometimes this interacts with a computer's built-in video hardware, limiting its resolution options. Thus, you might try fiddling with your firmware's CSM feature. (It's often called "legacy boot support" or something similar.) Note, however, that messing with these features can sometimes cause boot problems. It should be possible to get the system booting again if you run into problems, but some people have problems with this because changing the CSM settings may automatically change something else that you must change back manually.
Your hypothesis about a communications glitch with the monitor sounds plausible to me, too, although I've never run into this exact symptom because of such issues myself. You might try swapping out the cable if this is convenient, on the off chance that it's a little flaky.
Beyond that, you might also try playing with my rEFInd boot manager. Specifically, its configuration file (
refind.conf) has an option called
resolution that sets the video resolution. This resolution should be carried through to the Linux
efifb module, so adjusting it in rEFInd may provide the workaround you want. Note that you can try rEFInd by installing it on a USB flash drive or CD-R without installing it on your hard disk. (The rEFInd downloads page provides download images for both these types of external media.) One caveat is that rEFInd can only set resolutions supported by your EFI and video card. If you try to set an unsupported resolution, rEFInd will complain and display a list of supported resolutions.