Not sure why I haven't blogged this one before.
With Windows Server 2003 Sp1, MS decided to modify NTLM authentication behaviour (this also affects LDAP authentication) so that a user can use their old password for an hour to access the network after it has changed.
This is to allow things like service accounts to still be able to login while the new password propagates.
However, I've never been convinced that the case is there (why does kerberos not need it?).
To disable this feature, you need to modify HKLM\System\CurrentControlSet\Control\LSA\OldPasswordAllowedPeriod. This is a DWORD value.
Setting it to 0 means that you disable the use of old passwords.
If this value is not in the registry the default of 60 minutes is used.
See kb906305 for further details.