More info:

1) For the user in question, a newname account was created as a copy of their oldname account, then deleted. Then along comes me and renames the oldname account to newname.

I don't see why this should be a problem. It's all about SIDs anyway, right?

2) We have determined that none of our DCs knows anything about the oldname account.

I explicitly connected to them in Powershell, and ran get-qaduser oldname: All the DCs returned NULL

They all returned user objects for the newname.

3) The problematic SQL Server is not connecting to the same DC as the rest. However, it is connecting to a DC that we have verified in 2) above.

4) On the problematic SQL server, the oldname works with setuser!

On one of our other servers, both the oldname and newname work with setuser!!!

5) When we check AD for that newname from the Windows server on that SQL server, it correctly identifies the newname.

I can't think of anything other than SQL Server must be caching AD group memberships somewhere?