Feature "Menu Access Checking" if enabled in context with Themekey version 6.x-2.5 (and perhaps other versions) and Service Links as of version 6.x-2.0 causes Themekey switching to fail. See http://drupal.org/node/761332#comment-3663410.

The hint described below the "Menu Access Checking" feature of Global Redirect saying, "By default this feature is disabled to avoid any unexpected behaviour", is indeed a good hint.