Oh this cursed error! If you google it you will find tons of possible solutions that fixes this dreaded issue. In this short post I will describe what fixed the problem for me.
First a little background on previous events. One of our SQL Servers was rebuilt by creating a separate VM for it with the same name as the original after the original was taken offline.
Next day I am unable to use Windows Authentication to log into this new server. I get the Cannot Generate SSPI Contect message. I can log into the server itself and access the databases without any problem locally. I can even do that on someone else's computer, just not mine.
I play around with the setspn command line utility for a while but nothing helps.
Finally I log into the server using a SQL account. After that is successful I try the Windows login and finally, I'm in!
Such a simple solution. I hope this will help someone else too.