We encountered the following errors on two seperate farms with the same scenario:

The SharePoint people picker displayed the following error

The dutch language pack has been used but it says: Sorry, we’re having trouble reaching the server.

Fiddler

Fiddler is showing error 400 Bad Requests each time the people picker tries to contact the Active Directory

ULS Logs

Exception occured in scope Microsoft.SharePoint.ApplicationPages.ClientPickerQuery.ClientPeoplePickerWebServiceInterface.ClientPeoplePickerSearchUser. Exception=System.Security.SecurityException: Requested registry access is not allowed.

Original error: System.Security.SecurityException: Requested registry access is not allowed.

SocialRESTExceptionProcessingHandler.DoServerExceptionProcessing – SharePoint Server Exception [System.Security.SecurityException: Requested registry access is not allowed.

Scenario

We have installed SharePoint 2013 using SPAutoInstaller and configured the people picker using STSADM because we have a one-way trust domain.
The people picker has been configured using the default STSADM commands:

STSADM.exe -o setapppassword -password “*******”
stsadm -o setproperty -url <WebApp URL> -pn peoplepicker-searchadforests -pv “forest:<ForestNameA>,<UserAccount>,<Password>;forest:<ForestNameB>”

Solution
The only helpfull warning we get was from the ULS logs and the event viewer as the errors are also shown there. After verifying different access denied logs we saw that the portal account was trying to connect to a registery key that it had no access to. We solved this issue by adding the portal account to WSS_RESTRICTED_WPG_V4 in the Local Users and Groups manager. You will have to perform an IISReset after adding the user to this group! The user can be found after the IISReset: