Comment 4 for bug 182165

I finally found out what's the problem: I reverted the changes to gnome-settings-daemon/gnome-settings-multimedia-keys.c (see below) and it works!

These were the changes between 2.21.2-0ubuntu2 and 2.21.4-0ubuntu1:
--- gnome-control-center-2.21.4/gnome-settings-daemon/gnome-settings-multimedia-keys.c
+++ gnome-control-center-2.21.4.orig/gnome-settings-daemon/gnome-settings-multimedia-keys.c
@@ -45,11 +45,10 @@
 /* we exclude shift, GDK_CONTROL_MASK and GDK_MOD1_MASK since we know what
    these modifiers mean
    these are the mods whose combinations are bound by the keygrabbing code */
+#define IGNORED_MODS (0x2000 /*Xkb modifier*/ | GDK_LOCK_MASK | GDK_HYPER_MASK)
-#define IGNORED_MODS (0x2000 /*Xkb modifier*/ | GDK_LOCK_MASK | \
- GDK_MOD2_MASK | GDK_MOD3_MASK | GDK_MOD4_MASK | GDK_MOD5_MASK)
 /* these are the ones we actually use for global keys, we always only check
  * for these set */
+#define USED_MODS (GDK_SHIFT_MASK | GDK_CONTROL_MASK | GDK_MOD1_MASK | GDK_SUPER_MASK | GDK_META_MASK)
-#define USED_MODS (GDK_SHIFT_MASK | GDK_CONTROL_MASK | GDK_MOD1_MASK)

 typedef struct {
    GnomeSettingsModule parent;
@@ -696,13 +695,20 @@
       break;
    case HOME_KEY:
       path = g_shell_quote (g_get_home_dir ());
+ cmd = g_strconcat ("nautilus --no-desktop", path, NULL);
- cmd = g_strconcat ("nautilus ", path, NULL);
       g_free (path);
       execute (acme, cmd, FALSE, FALSE);
       g_free (cmd);
       break;
    case SEARCH_KEY:
+ cmd = NULL;
+ if ((cmd = g_find_program_in_path ("beagle-search")))
+ execute (acme, "beagle-search", FALSE, FALSE);
+ else if ((cmd = g_find_program_in_path ("tracker-search-tool")))
+ execute (acme, "tracker-search-tool", FALSE, FALSE);
+ else
+ execute (acme, "gnome-search-tool", FALSE, FALSE);
+ g_free (cmd);
- execute (acme, "gnome-search-tool", FALSE, FALSE);
       break;
    case EMAIL_KEY:
       do_mail_action (acme);

I'm quite certain that the problem is in the first to changes to the "#define" lines since the other changes were specific to the search and home keys.