Keybindings not working

PHPStorm is great on Mac, but is completely unusable for me on my Linux computer: all keyboard shortcuts with letter keys are not working (i.e. a..z, though digit keys, space, etc are OK).
When I press Ctrl+Space inside PHPStorm it tells me "No suggestions" which is OK, but when I try any of Ctrl+X, Ctrl+P, Ctrl+W, Ctrl+L, etc, it doesn't react in any way. All menu items, toolbar icons, mouse bindings are working alright.
I opened Settings -> Keymap and tryed to add new keyboard shortcut to one of the actions. Again, when I press Space, digit keys or Escape, PHPStorm understands it and shows it in 'First Stroke' window. But when I try on of the letter keys, it says: 'Unknown keyCode: 0x0'.

There is nothing special in idea.log. This bug doesn't affect Eclipse
I've tryed with both OpenJDK and Oracle/Sun, Fedora 15 x64 and Ubuntu 11.10 x64 (same machine).
Related issue: http://youtrack.jetbrains.net/issue/IDEA-75450

Please tell me I'm doing it wrong (or there is a workaround). Should I change my keyboard?

UPDATE: I was wrong about NetBeans - it is actually affected by this problem