Had the same problem and found it to be the KVM, once I plugged the monitor in directly during install I had no problems.
On the same note, I have two different cables on my DLink 4 Port KVM, the two that came with it, and two that I purchased later. The two skinny black ones that came with the DLink work fine, Mint detects my monitor through the KVM, and gives me 1280x1024. The two nice, big, thick, ribbon-cabled white ones . . no matter what I do, my monitor will not be detected, and a max of 800x600.
I have Vista running through the KVM too, and I can get the full monitor resolution through any of the cables.