Тоже подтверждаю, что проблема имеет место быть.
Но не везде, и от чего зависит пока не понял.
У меня на двух машинах стоит Ubuntu 9.04 amd64 с одинаковым (или почти одинаковым) набором пакетов.
На одном проблемы нет, на другом с недавнего времени появилась.
Причем у меня проблема с комбинациями из не менее 3-х клавиш.
Так, в моем случае все мультимедийные операции завязаны на клавиши Ctrl+Win.
Например, Ctrl+Win+Up - увеличить громкость, Ctrl+Win+Down - уменьшить громкость, Ctrl+Win+PgUp - предыдущая композиция в проигрывателе, Ctrl+Win+PgDown - следующая композиция и т.д.
Сейчас пришлось вместо Ctrl+Win назначить Alt+Win, так работает.
Причем на втором компьютере, как уже писал, все работает нормально.
Клавиатуры одинаковые (Mitsumi самые простые).