This is due to the site collection users list, which is where this info is stored. There are two timer jobs that control this:
"User Profile Service Application Name" - User Profile to SharePoint Full Synchronization
"User Profile Service Application Name" - User Profile to SharePoint Quick Synchronization
Where "User Profile Service Application Name" is the name of the user profile service application. The full runs hourly, the quick every 5 minutes. They require information about the user to be correct in the user profile store. I would be that is where your issue lies. The reason it works for new users added is because people picker is resolving the user info real-time from AD and not the user profile service application. Then once you select them and they login to the site, they are added to site collection users. Once they are added to the site collections users, that info is used instead. You can view the site collection users by looking a group id 0 on the site collection (easiest way to do this is open a group, then change the ID to 0 in the URL, and press enter of course).
A fix outside of user profile service application is deleting the users from the site collection users list and adding them again (slow, tedious and you need to make sure you add them to the right group(s) again).