This is usually related to user profiles and issues with synchronization.
You can proceed with the approach proposed by Trevor, or you can take a look at the user information list.
The basics of this list are explained Here.
Talking about a scenario where User Profile Sync is not set:
This list works as a "cache" with user data that is not syncd.
So, when some user logins into some sharepoint site or is referenced in some site (added to a group or referenced into a User column...)... sharepoint creates a record for that user into "User Information List". Basically it copies data from AD for that record.
So, if you look at this list, probably your users will have some attribute with those "old titles". This issue usually happens when users change e-mails or things like that.
Oh, configuring User Profile Synchronization service is also a good deal.