So, hat ewig gedauert, aber ich habe das Problem gelöst:
Am Domain Controller (bei uns Windows Server 2008r2) unter Active Directory - Benutzer,
Eigenschaften von "Hein Blöd" - Konto - Kontooptionen - Haken bei
"keine Kerberos-Präauthentifizierung erforderlich" setzten.
Kleine Haken, große Wirkung.