Путем продолжительного гугления узнал, что это проблема иногда встречается у пользователей Arch, причем иногда не работают обе клавиши Win, а иногда - только левая.

В моем случае не работала только левая клавиша.

В официальной Archwiki написано только о том как заменить Win клавишами Ctrl
http://wiki.archlinux.org/index.php/Xmodmap, но мне такой вариант не подходит, так как в одно время был пользователем awesome, а в этом WM, как известно, все клавиатурные привязки связаны с клавишей Win. Ну и, как говорится, привык. Теперь, где бы я не работал, а сейчас работаю в Xfce, всегда назначаю себе привязки сходные с awesome.

Пришлось зделать немножко не по Wiki. Опишу по порядку.

1. Выгрузил в файл таблицу клавиатурных кодов

xmodmap -pke > ~/.Xmodmap

2. Проверил командой xev коды клавиш Win

Вывод показал, что они соответствуют кодам 115 и 116, а для правой, вместо Super_L, назначена Multi_key

3. 
vim ~/.Xmodmap

4. В файле оставил только две строчки, касающиеся кодов 115 и 116

keycode 115 = Multi_Key NoSymbol Multi_Key NoSymbol Multi_Key
keycode 116 = Super_R NoSymbol Super_R NoSymbol Super_R

5. Добавил в начало файла ~/.Xmodmap: 

clear Mod4

6. Заменил Multi_Key на Super_L

keycode 115 = Super_L NoSymbol Super_L NoSymbol Super_L

7. Проверил изменения: 

xmodmap ~/.Xmodmap

8. Добавил эту команду в автозапуск.