An important question for all experiencing this issue:
How many of you have the following GPO setting for your domain controllers defined: Computer Configuration\Policies\Windows Settings\Security Settings\Local Settings\Security Options--> Network Access: Restrict Clients Allowed to Make Remote Calls to SAM Enabled, Security Descriptor = O:BAG:BAD:(A;;RC;;;BA)(A;;RC;;;
Though some of you may have compliance/regulatory concerns by changing this, if you add the AD group that needs the Reset Passwords permission, those users should be able to reset passwords again. If some of you are unable/unwilling to do this, I've found that resetting passwords via the Active Directory Administrative Center is a viable workaround.