I've got the same problem at the moment. Also using MATE, also worked when I was on GNOME3. I just wish I had a product key I could use to refer to my computer, like the above two
System: Host burrito-linux-desktop Kernel 3.0.0-12-generic x86_64 (64 bit) Desktop N/A Distro Linux Mint 12 Lisa
Machine: Mobo ASUSTeK model M4A78LT-M version Rev X.0x Bios American Megatrends version 0802 date 08/24/2010
CPU: Dual core AMD Phenom II X2 555 (-MCP-) cache 1024 KB flags (lm nx sse sse2 sse3 sse4a svm)
Clock Speeds: (1) 3200.00 MHz (2) 3200.00 MHz
Graphics: Card: nVidia Device 1245 X.Org 1.10.4 drivers nvidia unloaded: nouveau,vesa,fbdev Resolution 1280x1024@50.0hz
GLX Renderer GeForce GTS 450/PCI/SSE2 GLX Version 4.1.0 NVIDIA 280.13
Audio: Card-1 ATI SBx00 Azalia (Intel HDA) driver HDA Intel Sound: ALSA v: 1.0.24
Card-2 nVidia Device 0bee driver HDA Intel
Network: Card Realtek RTL8111/8168B PCI Express Gigabit Ethernet controller driver r8169
IF: eth0 state: down speed: 10 Mbps duplex: half mac: [REDACTED]
Drives: HDD Total Size: 496.1GB (36.2% used) 1: /dev/sda WDC_WD3200BEVT 320.1GB
2: /dev/sdb SAMSUNG_HM160HI 160.0GB 3: USB /dev/sdc STORAGE_DEVICE 16.0GB
Partition: ID:/ size: 61G used: 11G (18%) fs: ext4 ID:/boot size: 92M used: 29M (34%) fs: ext4
ID:swap-1 size: 2.15GB used: 0.00GB (0%) fs: swap
Sensors: System Temperatures: cpu: 40.0C mobo: 42.0C gpu: 35C
Fan Speeds (in rpm): cpu: 2586 psu: 0 sys-1: 0 fan-2: 0 fan-3: 0
Info: Processes 179 Uptime 12:09 Memory 1276.4/3960.6MB Client Shell inxi 1.7.7
edit: I've found a very temporary 'fix' for it - if you keep Audacious running (make sure it is not using 'software volume control' by unticking the relevant option in Preferences > Audio) and enable the plugin called 'Global Hotkey' and assign shortcut keys through that, it should work. Working for me.