ORA-12631: Username retrieval failed

Case:
While attempting to connect to the database the following error occurs.

c:\temp\dig>sqlplus /@qanew as sysdba

SQL*Plus: Release 11.2.0.1.0 Production on Tue Oct 2 09:09:07 2012

Copyright (c) 1982, 2010, Oracle.  All rights reserved.

ERROR:
ORA-12631: Username retrieval failed
 
Cause
The database server is  a member of a MS Windows Domain and the Oracle Service was started before the NTLM service or the NTLM service is not started at all.

Solution
1) Reboot the machine
or
2) Restart the Oracle Service after making sure that the NTLM service is started. 
 
Additional Observation If you try to connect with other user (not sys) with DBA role granted then you are connected and you get the info that instance was crashed.

c:\temp\dig>sqlplus inam/pwd@qanew as sysdba

SQL*Plus: Release 11.2.0.1.0 Production on Tue Oct 2 09:24:15 2012

Copyright (c) 1982, 2010, Oracle.  All rights reserved.

Connected to an idle instance.

Some Info about NTLM

In a Windows network, NTLM (NT LAN Manager) is a suite of Microsoft security protocols that provides authentication, integrity, and confidentiality to users. is a challenge-response authentication protocol which uses three messages to authenticate a client in a connection oriented environment , and a fourth additional message if integrity is desired.

First, the client establishes a network path to the server and sends a NEGOTIATE_MESSAGE advertising its capabilities. Next, the server responds with CHALLENGE_MESSAGE which is used to establish the identity of the client. Finally, the client responds to the challenge with an AUTHENTICATE_MESSAGE.