This sounds scarily like a KB article, which I don't do, so we'll just jump straight to the facts.  I noticed that after I applied the April 2014 CU to my farm that hybrid inbound search no longer worked.  I subsequently confirmed with some other folks that they were seeing the same issue as well after applying that CU.  What ends up happening is that you'll see a 401 unauthorized error if you try working with the query in the query rule editor.  If you look on the on prem farm you'll see the following error messages in the ULS log after you try and pull query it from o365:

Error trying to search in the UPA. The exception message is 'System.ArgumentException: Exception of type 'System.ArgumentException' was thrown.
The set of claims could not be mapped to a single user identity. Exception Exception of type 'System.ArgumentException' was thrown.  Parameter name: value has occured.
The registered mappered failed to resolve to one identity claim. Exception: System.InvalidOperationException: Exception of type 'System.ArgumentException' was thrown.  Parameter name: value

For now, some bright individual has come up with a work-around for now that will get your inbound queries working again.  You just need to run the following PowerShell script once in your farm:

$config = Get-SPSecurityTokenServiceConfig
$config.AuthenticationPipelineClaimMappingRules.AddIdentityProviderNameMappingRule("OrgId Rule", [Microsoft.SharePoint.Administration.Claims.SPIdentityProviderTypes]::Forms, "membership", "urn:federation:microsoftonline")
$config.Update()

That should fix it for now, I don't know if all of this will rolled into some future CU, but you at least can get back to working with hybrid for now.