1. Such problem emerge because of the application pool account of the lms web application doesn’t have sufficient permissions to search users from the needed domain.
2. Also the reason may be that learners are from different domains, i.e. app pool account is in one domain and learner in another. And domain trust is not configured between them: http://technet.microsoft.com/en-us/library/cc961481.aspx
It is preferred to have two-way trust between domains.
Absence of two-way trust result into situation that app pool account tries to resolve users from another domain, but another domain doesn't allow to do this, because this domain doesn't trust the domain where LMS app pool account is. (note: all the LMS code is run by app pool account).
To verify the 1st possible reason do the following:
1. Download and launch AD Explorer under app pool account (may be done even on client machine but in the same domain)
2. In AD Explorer connect to necessary domain under app pool account.
3. Right click on the domain name -> Search container
4. In Search Container dialog add attributes: objectCategory=person and objectClass=user
see screenshot for how added attributes should look like in the "Current Search Criteria" area:
5. Click Search
If the search was successful then app pool account has permissions to search users in domain and you should check 2nd possible reason.
If the search wasn't successful then you should give such permissions to the app pool account of the lms web application.