I see that this question has been asked before. But I don't think it is the same conditions. We have two new users who where set up in AD incorrectly. Lets say account 001 was named for John Smith and account 002 was named for Mike Jones. The mistake was caught by our AD people, and they corrected it by naming 001 for Mike Jones and 002 for John Smith. However, they still appeared wrong in SharePoint.
I went to the SSP, deleted the profiles of both users, then did a full import. When it was done, the profiles showed correctly in the SSP. I went back to the web application to add them in, and they still came up wrong.
Now the really strange part. This web app is made up of dozens of site collections. I look up their names in one, they are wrong. I look up their names in another, they are right.