"You are not authorized to change your password at this time"

From: Mike Matheny (tmatheny_at_emsdotjscdotnasadotgov)
Date: 11/24/04 

Date: Wed, 24 Nov 2004 15:11:20 -0600

AD domain mixed mode - users off-site via T-1, no DC on site. Everyone gets
this error when prompted to change their password at logon, some get it
trying to change the password after logon. Complex passwords enforced - even
using a completely different password doesn't work.

Any ideas would be awesomely appreciated. 

-- 
Mike Matheny