Did this happen after applying SP4? I am assuming that this never worked. If yes, then there is something wrong with Active Directory.
please check the following.
1. Version of 'xpstar.dll'
2. What is the Startup account of SQL Server?
3. Does startup account has proper persmission on Active directory?
4. Change Startup account to local system account and see if that works?
Feel free to ping me at bmlakhani@yahoo.com