Linux: Key presses won't register for ~500 ms if two (or more) keys are pressed on the same frame

Since the last update, I had trouble moving around in the game. I narrowed down the problem to this:

When one presses two (or more keys) in the exact same frame, only one of those gets registered. For instance, pressing A+D will cause the player to strafe left, instead of diagonally.
However, after about 500 ms, the second key gets registered (as if the game behaved like a text editor, only registering a key being held down after it has been held down for a while).
If the two keys are pressed at slightly different time, everything works perfectly.

This makes it impossible to perform basic actions such as jump+forward+sprint to get over large gaps without a run-up.

The included H.264 video file is a demonstration of this behavior.