I have a similar set-up to yours using a Linskys KVM2KIT KVM 2-Port Switch.
When I experienced exactly the same symptoms I suspected the new Microsoft keyboard I was using, no problems earlier with my original keyboard. The Linskys unit requires the scroll lock key to be pressed twice to change over machines.
Interchanging keyboards made no difference, I then disconnected the KVM and proved both machines separately. Re-connected the KVM and, touch wood, no problems since. As I had checked all connections previously I'm still at a loss to explain what the 'cure' was!