Got this error a lot when trying to add NT user accounts on a SQL Server 2008 installation that was connected to a Windows 2008R2 server running Active Directory 2008 at Windows 2000 functional level.  Same error message appeared when troubleshooting this from a SQL Server 2005 instance in the same server environment.

You’ll keep getting “Windows NT User or group ‘MyDomain\MyUser’ not found. Check the name again. Microsoft SQL Server, Error: 15401″

Here is a link to the solution that worked.