Hi,
There's a couple of things I'd check to start with - first, check that the case is right when you're searching for the username, because the search is case-sensitive. If the user has any publically shared items, you could also try searching for those items by using a search string like:
owner:username
That way you could be sure the username was correct.
Second, I would go to the ArcGIS Online website, and check if you can invite the user that way, to rule out any problems with using ArcGIS Explorer Online.
Hope this helps,