I have encountered this exception while I was trying to create ‘Search Service Application‘ in SharePoint 2013.
Surprisingly many encountered this particular exception at completely different instances /scenarios.
For instance, some faced while running through SharePoint Configuration Wizard steps and some while creating Service Applications. Based on my understanding this is commonly encountered on STANDALONE instances, primarily set up for development. You might NOT face this issue at an enterprise level SharePoint farm, you would get to know why, by the end of this blog.
Following are two common instances along with resolution.
Running the SharePoint Configuration Wizard.
I have set up my whole SharePoint Farm via PowerShell scripts and did not encounter this. But following solution from Microsoft Technet, worked perfect for many. Hope this resolves your issue.
2. Creating Service Applications
Following is screen capture of the error message
Resolution: Set up your Domain Controller
When I spun up SharePoint 2013 on my Azure VM, I did not configure my Domain Controller which appears to be prerequisite for certain functionality to work with in SharePoint 2013.
If you closely look at the portion of the exception in the above screen capture, you will find “Invalid sid or a sid that cannot be translated“. These issues are encountered when Domain Controller is not configured correctly.
A security identifier (SID) is a unique value of variable length used to identify a trustee. Each account has a unique SID issued by an authority, such as a Windows domain controller, and stored in a security database. Each time a user logs on, the system retrieves the SID for that user from the database and places it in the access token for that user. The system uses the SID in the access token to identify the user in all subsequent interactions with Windows security. 
Finally after exhaustive research and understanding, I resolved my issue by creating the domain controller. Please following instructions at Windows Server 2012: Set Up your First Domain Controller (step-by-step) to set up your domain controller.
After this is complete my Central Admin and all my web applications were working fine.
But when I started continuing to create my Search Service Application, I got hit by another minor error. Since I did not start off with Domain Controller, all my accounts were in “MachineNameusername” format, so the SQL server still got the old username, so modified it to “DomainNameusername” and everything worked seamlessly.
I was so glad to see this working, I was working on this issue stubbornly, sacrificing super bowl 2015. At least it payed off!