Does your KVM switch pass the monitor EDID data through to the computer? I also run a KVM which blocks the EDID data which means that Xorg cannot autodetect the monitor. Some xorg.conf magic is required to get reasonable resolution and refresh rates.
I've run this KVM pretty well from the time I started using Ubuntu, since I needed my Windows production machine at the time for work. These days Windoze is gone, but the switch lives on as it lets me switch between my production machine the testing machine with three different partitions.
Interestingly, the way I had to write xorg.conf changed drastically with the change to 11.04 Natty. Where previously it was very simple, Natty broke this system and required a lot more work to figure out.
Simple is deceptive though. It took me weeks to figure it out as an Ubuntu Noob, but only a day to figure out the new settings required for Natty.