If a user's account gets deleted and then re-created with the same name you will have an orphaned account in the User Profile Database. The SID's will be different. To confirm the different sid's, open the Active Directory Console for PowerShell and type the following:
Notice the SID:
Then open the SharePoint console and retrieve the user into a var. For my farm the login name is domain\samAccountName
$u = Get-SPUser -Web "http://focas" -Identity "UserLogin"
The sid's are different even though the SamAccountName is the same.
You can fix the problem using stsadm -o migrateuser or you can choose the updated PowerShell equivalent: Move-SPUser
Move-SPUser -Identity $u -newalias "domain\samAccountName" -IgnoreSID
Afterwards the SIDs between SharePoint and AD should match.
This is a good article on the updated commands that replace the stsadm commands.