Lync LS Storage Service 32054 and 32053 errors (Solved!)

A customer wanted me to look into an issue with singning onto Lync 2013 remotely with a Lync mobile client for Android. Lync is updated with CU2.
The lync client could sing on but a error message was shown in the client.
"Invalid Exchange login credentials"

Error shown in Norwegian

A look at the errorlog on the front end server showed these error messages:

• Storage Service had an EWS Autodiscovery failure
• Microsoft.Rtc.Internal.Storage.StoreConfigException: No issuers are accepted by the target server, expected 1-many accepted Issuer(s)Storage Service had an OAuth authentication failure.

I ran the powershell command:

Test-CsExStorageConnectivity -SipUri jeti@customer.no -Verbose

It failed with this response:
2013.08.28 10:07:01.750 OAuth.CreateAppActAsToken failed,
ex=StoreConfigException: code=ErrorOAuthConfigIssuer, reason=No issuers are
accepted by the target server, expected 1-many accepted Issuer(s)

I then went focused on the partership between the lync fe and the exchange-server.
First the prerequisites mentioned here

Then the nest step mentioned here
I ran the script on the Lync frontend server and the powershell command "c:\Program Files\Microsoft\Exchange Server\V15\Scripts\Configure-EnterprisePartnerApplication.ps1" -AuthMetadataUrl "https://lync.contoso.com/metadata/json/1" -ApplicationType "Lync"
on the frontend server but still no luck.

Seems like more people are experiencing the same issue is this blog: Multiple LS Storage Service 32054 errors

Update:
Solution from Microsoft to this problem is found here: http://support.microsoft.com/kb/2905047/en-us

Second Update: http://blog.insidelync.com/2012/08/the-lync-2013-preview-unified-contact-store-ucs/

In this article it describes the following solution to this errors:

Check to see whether you have Event-id log errors 32054, 32053, and 32045 in the event log (under the ‘Lync Server’ application node).  Looking at the contents of these errors you will likely see an oAuth authentication failure.

This is a frustrating error because of the wrong error message returned by the Test-CsExStorageConnectivity cmdlet.  The real problem is that the Network Service account that the Lync Storage Service uses does not have access to the private key in used by the oAuth certificate. I found the solution in this Lync Server 2013 Preview Forum posting:

1. Open MMC and add the “Certificates” Snap-in (Local Computer)
2. Open Personal | Certificates and find the the Certificate being used for OAuth (use the Lync “Get-CsCertificate -Type OAuthTokenIssuer” cmdlet to find the serial number of the OAuth certificate).
3. Right-click | “All Tasks” | “Manage Private Keys”
4. Add Permissions for “Network Service” account (the defaults Full control and Read).

Note: if this was not the problem, test that you can browser to the Exchange Server 2013 autodiscover metadata URL in IE without any certificate warnings or errors (e.g.https://autodiscover.myDomain.com/autodiscover/metadata/json/1).

Tip: if you are having further problems with application pool trusts if you are trying to configure OWA integration, see “When to have a Lync Trusted Application Pool for Exchange OWA IM Integration?” by Jens Trier Rasmussen.