User Windows login name has been changed in AD yet session in SQL 2008 Profiler shows the old Windows login name

I guess I can't comment on your question since this is the first time I've used stack exchange but is this an AD group that the user is in? Sometimes people say group when they mean SQL role so I just wanted to get some clarification.

The reason I ask is because if the user has a login on the server of domain\olduser when you change the name in AD to domain\newuser you have to go into SQL and change the login to domain\newuser. I've done this and it works perfectly fine and you don't have to do anything as drastic as restart SQL. I do not know if the account name will eventually change to the new one over time but my guess would be no.

I do not know, however, what happens when the user is just part of an AD group that has permissions and doesn't actually have a login on the server. Hence the need for clarification so I can look into that.

I ran into the same problem in a SQL Server 2012 instance (SP2 applied). I haven't found the root cause yet, but we will be looking at the AD caching mechanism, as suggested by StanleyJohns.

By accident I have found a simple solution that worked for me without rebooting the server. I created a Windows Authenticated login for the old username (yes, that worked) and then dropped it - problem solved.

After the create / drop I was unable to create the same login a second time, so it looks like the "drop login" is another way of forcing the old username out of the AD cache.