I have found a problem when SharePoint 2013 is installed on a French operating system (Either Win2K8 R2 SP1 or Win2012).    With this setup when you enable anonymous access to a SharePoint Site everything seems to be working while accessing the site anonymously, except search.  When you display the Search Results page or a page with the Search Results Web Part in it, you get the following message:

Search Error

The ULS logs are not helping.  The only interesting information I have found is: The security token request cannot be completed.

Note: The issue is not there when SharePoint2013  is installed on an English OS.

We have opened a ticket with Microsoft.

Will keep you posted.