There are really normally two bugs involved. The first bug is that Gnome doesn't think the Win key is a modifier, so it registers as Super_L (meaning the Left Super Key as a standalone) whenever you try to bind a shortcut using that key. This can be fixed through System -> Preferences -> Keyboard -> Layout Options -> Alt/Win Key Behavior. Choose the option labeled "Super is mapped to the Win-keys (default)" Yes, I know it says default, but it isn't really. You'll notice that one or two other options in the same series are also labeled default.
The second bug is that there are two separate shortcut managers, metacity and gnome-settings-daemon, and one of them (gnome-settings-daemon) happens before gnome does its magic modifier mappings, the other happens after. Basically this means that when you set the key bindings under Keyboard Shortcuts in preferences, you are using a certain key layout when you make your selection, but when the keys actually get interpreted, they are using a different (and defective) layout, which lacks certain keys -- such as the Windows key. So far, there's not really a good way to fix the problem, but there is a way to work around it. Instead of letting gnome-settings-daemon handle the task you are trying to assign, find an alternate way to perform the task using metacity (or compiz). Open up gconf-editor from a terminal, then go to /apps/metacity/global_keybindings where you will find a series of run_command_X options from 1 to 12. Fill in one of them with the value
/usr/bin/gnome-screensaver-command --lock
This will launch the gnome screensaver and lock the screen.
I know this isn't perfect, but a workaround is better than nothing. I hope it was helpful!
