1. Alt+F2, run command:
gconf-editor
2. Goto key: '/apps/metacity/global_keybindings', set 'run_command_1' value to 'R'
3. Goto key: '/apps/metacity/keybinding_commands', set 'command_1' value to 'gnome-terminal'
4. Now close the editor and press Win+R, see what happens. HTH