Hmm, it's usually the KVM being of sub-optimal quality.
If the KVM was just a straight pass-through for input devices, there should be no problems. Once "features" start getting added, then issues can arise like bizarre polling, repeat key presses, let alone supporting NKRO.
I really haven't used USB KVMs that much (though I've known people who've had problems with them on typical rubber dome keyboards).
My advice would be to use PS/2 if possible (still potential problems though, just not as many of them).