SAML Subject NameIdentifier missing required NameIdentifier value

[Andrei Remenchuk]

We're integrating our Shibboleth SP with IdP belonging to another 
organization.
The user is redirected to IdP web site and successfully authenticates 
there.
The IdP however, doesn't redirect back to SP site, and gives the 
following error in the browser:

         SAML Subject NameIdentifier missing required NameIdentifier value

I am trying to understand where the problem is - on our (SP) side, or on 
IDP side, and if the problem is on our side, then what can we change in 
SP configuration to satisfy this IDP. Similar setup works fine with 
other IDPs.

Here's our outgoing SAML request for this particular IDP:

<samlp:AuthnRequest xmlns:samlp="urn:oasis:names:tc:SAML:2.0:protocol" 
AssertionConsumerServiceURL="http://xxxxxxxx.xxxxx.com/Shibboleth.sso/SAML2/POST" 
Destination="https://sso.xxxxx.edu/nidp/saml2/sso" 
ID="_458a0c982ec1c219ce45839f0225a1d2" 
IssueInstant="2016-01-21T19:16:53Z" 
ProtocolBinding="urn:oasis:names:tc:SAML:2.0:bindings:HTTP-POST" 
Version="2.0"><saml:Issuer 
xmlns:saml="urn:oasis:names:tc:SAML:2.0:assertion">urn:xxxx:shibboleth:xxxx:xxxxx.com</saml:Issuer><samlp:NameIDPolicy 
AllowCreate="1"/></samlp:AuthnRequest>