Check your time on the DSS server to make sure it is the same for the ADS server. Check that you have the DNS settings in the DSS server to have the ADS sever as well - you can have more then 1 entry.
Should have had that in my post. Time was fine and ADS server was in the list. I redid the ADS admin login in Setup>Administrator and that fixed it for now. However why this server and not the other had this problem is a mystery at the moment.