That is strange. My old cheap Nextech KVM worked fine with DVI -> VGA. I only stopped using it because it was PS2 only and my screens had multiple inputs(single button switch from pc to pc).
I used one of these
(well one that had only 4 ports, but later picked this up when it was on clearance[my 4 port one still worked, but the switches had started to stick]) to take care of the switching mouse/keyboard/card reader/ect. Nice thing is it can switch each device.