DISCLAIMER: This answer involves manually editing the Sharepoint site information database.
In SQL Server Enterprise Manager, open the _SITE database for your Sharepoint implementation. Query the UserInfo table in the following manner:
WHERE (tp_Login = ‘oldlogin’)
(You can first use SELECT TOP 5 * FROM UserInfo to see how the logins are formatted.)
For each entry of the old login, replace the value (tp_Login) with the new login.
Solved our “User cannot be found” errors related to a change in AD not correctly propagated to Sharepoint.