Just to make some things clear about keyboard shortcuts. Many shortcuts can be changed by right-clicking on the app, writing in the new desired one in the form <Alt><Shift>7 or whatever. If they don't work immediately, try logging out and back in again, if they still don't work try rebooting. MintMenu is like the last one. It evidently loads early in the boot process and merely logging out and back in again will not reset it -- but rebooting will.
If your desired shortcut still will not work, it may be in conflict with something else. Maybe that shortcut has already been used for something else. Gnome might tell you when you try to set it, but if not you might have to dig around. A good rule of thumb is not to use really common ones like <Ctl>z for example. If you have Compiz active, it over-rides existing identical shortcuts set in Metacity (the Gnome configuration app). For example, <Alt>Tab is the well-known shortcut key to activate and page forward through open apps. Usefully, it works the same on Windows, Mac and Linux (the Mac key of course is not "Alt" but "Command" -- it is in the same place on the keyboard though). Not so usefully, the keys to page backwards (reverse, move right to left), are different on the various OSes. I like the Mac solution, which uses <Cmd>grave (grave is the key right above the Tab key). But to set Mint to <Alt>grave one has to do it in Compiz, I think in the Window management section. Hope this helps, and if I erred in any part, please correct me. I've used various debian linux distros quite a while, but Mint only recently.