So there's this really annoying bug that a lot of GNOME users have been experiencing, including myself. The first issue is that the default GNOME layout binds the "Windows" key to Super_L/Super_R, which prevents you from using it as a modifier key. This is a relatively easy fix; run gnome-keyboard-properties and change "Layout Options->Alt\Win Behavior" to "Meta is mapped to the Win-keys" (or just about anything other than "Default", apparently). Now, you can open up gnome-keybinding-properties and use away. But wait! It mysteriously only works for some of the actions. This is because essentially two keybinding backends are used, gnome-settings-daemon and metacity. Turns out, gnome-settings-daemon ignores Mod4 (which is what the Windows key gets mapped to as a Meta). Thankfully, it's an easy fix! Grab my patch or if you're running Ubuntu/Debian, you can install these deb's which already have the patch applied and restart GNOME (these have only been tested on Ubuntu Hoary). Now, rejoice that you can finally have Windows+L mapped to "lock screen"!