This was a strange issue that fortunately has a technote for it…
We had a person who used to be a contractor and then subsequently became an employee in a different area. They were added to a particular site with Contribute level access, but whenever they tried to get to the site, they’d get an access denied message. In Active Directory, they had the correct information for their new position. Their My Site had all the right profile information. But when I’d use the People and Groups dialog box to add them to the site, they’d show up with the contractor information. It was as if the person in that site was different than the person we were trying to add.
After some searching (and flailing for the right combination of keywords), I found a technote from Microsoft that explained the issue:
A user in your organization has recently updated some of his or her information (such as the user’s display name) in Active Directory Domain Services. The information was updated correctly in the user Profile Service Application. However, on a specific Microsoft SharePoint 2010 Site Collection, that information was not updated.
The key is to remove them from the All People group in the Site Collection, which can be found in SharePoint 2010 at <Site URL>/_layouts/people.aspx?MembershipGroupId=0.
Once I did that and then re-added them, their information was correct, and they could access the site with no issues. Whew!