Our sharepoint farm was in Domain A and we wanted to grant rights to a group in Domain B.
It worked fine from the GUI but powershell add-spuser or new-spuser failed – both stating the user ID we were adding was no good.
Specifically this was for Mysites – we had thousands of them so doing it by hand wasn’t an option.

$app = Get-SPWebApplication -Identity https://www.siteInDomainA.com
foreach($site in $app.Sites)
{
    write-host "Updating $site"
    $web = $site.RootWeb
    $web.AllUsers.Add("DomainBDomain Users", [System.String]::Empty, "Domain Users", [System.String]::Empty)
    Set-SPUser -Identity 'DomainBDomain Users' -Web $web.Url -AddPermissionLevel 'Read'
}