This has happend twice now, once on a SQL 2008 64-bit VM and once on a different SQL 2008 R2 64-bit VM (different AD logins each time, too).
We have an AD login on the server, and when we try to connect via Windows authentication as that login we get "login failed for XXX\ADUser." If we drop the login and add it back, it then works. When this first happened I thought it was a fluke, but it has happened to us twice. I searched the Internet and I found this reference to the same problem: