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.

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 a way of forcing the old username out of the AD cache.