Welcome to LQ! Several years ago I had a similar problem with a Belkin KVM, where I had connected one Windows machine and one Linux machine. Basically, regardless of which machine I started from, I could always toggle over to the other machine successfully, but on the return trip, the keyboard and mouse would die (video was fine however). The only way I could fix it would be to reboot, which was incredibly frustrating and pretty much defeated the purpose of having the KVM in the first place. My eventual solution was to just dump the Belkin and replace it with a different brand/model (a Trendnet TK-401R if you're interested) The complicating factor as I see it is just that because a KVM is external to the box, and (to my knowledge) there aren't really any "KVM configuration" settings in either Windows or Linux, it just wasn't something that I could adjust.
Maybe things have changed since I was dealing with it, and hopefully others will have better recommendations than my admittedly feeble "solution", but FWIW that was my experience. Good luck with it