I am using a linksys (I think) KVM at home (at work now and I thought I was having the same problem. My KVM switched by pressing scroll lock twice. After some fooling around I realized that when it seemed like it was frozed I often neede to press the scroll lock button one more time. Also I've noted that booting linux while switched to the other system == bad, so I always have to sit an watch linux boot (windows doesn't seem to have this problem), hope it helps you

-Kaplanfx