Very odd server issue

i concur with checking the domain security policy then. this change could have been made months ago, but some policy changes won't affect the server until they have been restarted. any recent updates requiring a reboot?

i'd start by opening the gpe (or ad users/computers since it is a 2003 level) and checking the security settings