Here is a solution that doesn't require fiddling with system settings. Tested on Mint 14 MATE, but should work on Cinnamon too.
- Right-click on Menu icon on bottom left of desktop
- Click "Preferences"
- In the initial "Main button" tab, click in the field to the right of "Keyboard shortcut"
- Press a new hotkey combo (I chose ctrl+win+space)
Voila - there are now hotkeys for the menu as well as Gnome Do.