I saw this problem a few times but when I went to user profile, I can see the user is there and all the information is right. But if you go to WSS_Content db and run
select * from userinfo where tp_title like ‘user%’
I found the tp_login data is different from the user who has problem. The problem with this, is that the tp_Login column in the UserInfo table for every site collection in which Margie has permissions, is cached with her previous NT Login Name. There is also no way to update this information with a SPUser object from the SharePoint object model, and SharePoint does not synchronize this from Active Directory once the users is added to a web in the Site Collection.
The only time that SharePoint will automatically update the tp_Login column, is if the users is completely removed from the site collection. The tp_Deleted column is then set for the user in that site collection. On the next occurrence of the user being added to a web, we gather the current information from the domain. You can however, re-sync SharePoint with the current information without removing them completely from the site collection by using SPUserUtil
For a single user you can use
stsadm.exe -o migrateuser -oldlogin MYDOMAIN\prhranki -newlogin MYDOMAIN\LUHRANKI -ignoresidhistory
If you need to do a batch of users, I personally think WSSUserUtil and SPSUserUtil is the way to go.