HOWTO: Windows Key & L to Lock Screen
There seems to be a bug in Gnome / Metacity / X somewhere that means you can't use SUPER_L or SUPER_R (the left and right windows keys on a keyboard) with gnome system commands such as "Lock Screen".
So, to get it working, you can follow these steps
Go to Desktop > Preferences > Keyboard (or run gnome-keyboard-properties) then choose the Layout Options tab and under Alt/Win key behaviour select "Super is mapped to Win-keys".
Start Configuration Editor (gconf-editor) and select apps/metacity/global_keybindinngs.
Create a new key called "run_command_15" of type String with value "<Mod4>L".
Now in apps/metacity/keybinding_commands create a new key called "command_15" of type String with value "gnome-screensaver-command --lock".
You can repeat these steps to create as many other keybindings as you like. I don't know the steps on KDE, but I believe KDE has much better keyboard shortcut support than Gnome.
It took me hours to figure all this out, hence my post here. Comments / feedback most welcome.