The INTERACT_ACROSS_PROFILES perm is needed for the new googlequicksearchbox app that was updated recently.