The KVM is actually working reasonably well. The following strategy seems to work on the PC: Boot it with the switch set on the Mac, and then only after Windows has gotten to its login screen, switch to the PC. This seems to result in the PC most often finding the USB devices (keyboard and trackball) and both the Mac and PC regaining the use of them when I switch between the two.
I'd still like to try replacing the video cables at some point in the future to see if I can get a better image, but I'm a perfectionist... I should probably let it go! Or, if I really want a better image, put that money towards a big LCD monitor.