The user does not exist or is not unique.

Past one week, I was struggling to get the solution of this problem related to SharePoint.
Problem #1: Whenever I try to add a user to a SharePoint group, if the user exist in the site collection, then I get this specific error.
Problem #2: Whenever I try to add a user to a SharePoint group, and if the user DOES NOT exist in the site collection, then I am unable to add the user at all because SharePoint in unable to communicate with Active Directory for name resolution.

These two specific problems were giving me very hard time. Let me give a brief about the environment here:
Web Front End (WFE) Server: 64-bit machine with 64-bit software. Windows Server 2008 R2, Office SharePoint Server 2007 Standard Edition with SP2 (version 6421).
Database + Reporting Server: 64-bit machine with 32-bit software: Windows Server 2003 Enterprise Edition, SQL Server 2005 with SP2, Reporting Services (with SharePoint Integration Mode), Reporting Services SP2 is applied.
Authentication Mechanism: Kerberos. [Very important here, because in windows NTLM authentication, AD link is working]

After struggling for 10 days, I finally open up the ticket with Microsoft to get the solution, and it is fixed after spending more than 24 hours. I interacted with SharePoint Team, IIS Team, Directory Services team, and but this problem is not related to any of these, it is a feature of Windows Server 2008 (and R2 too) which does not work with SharePoint Server 2007 OR the applications that are built on Windows Server 2003 based application. It is a local policy in 2008 R2 that is required to be disabled (and machine restart is required after reset).
This policy name is "Domain member: Digitally encrypt or sign secure channel data (always)". It is Enabled by default when you configure Windows Server 2008 R2.
How to reach to this policy: Start -> Run -> type gpedit.msc.
Browse to Computer Configuration -> Windows Settings -> Security Settings -> Local Policies -> Security Options. Under Security Options on the right hand side, you will find this policy.
Double click to open the policy, Click 'Disable' radio option. Save the changes and restart the machine.

Earlier to this solution, did following checks though:
1. people picker property is correctly set.
2. Domain Controller is receiving request and responding it back using Network Monitoring Tool.
3. Port Qry UI - A tool that helps to check what ports are responding for kerberos Authentication mechanism.

One very good article that is worth reading: http://support.microsoft.com/kb/823659.

Hope this will help somebody who have Windows Server 2008 R2.