Even though you say you checked the group memberships, it really sounds like your "admin" account doesn't have the same group memberships as the "Administrator" account.
The Windows "whoami.exe" (not the Cygwin whoami) with the "/ALL" parameter will show you each user's group memberships so that you can compare them.
(In theory, it would be possible to modify the permissions of user objects in AD to deny the "admin" user rights to change their password while still having "admin" be members of the same groups as "Administrator", but I think that's highly unlikely.)
To rule out anything to do with the cygwin SSH altogether, why not logon locally to the server comuter with the "admin" credential and try your "NET USER" from an NT command prompt?
There really isn't any kind of group policy setting that affects the ability to change passwords, per se. If your "admin" account is a member of "Enterprise Admins" it should be able to reset the password of any other account in the Active Directory. Like I said above, there are "tweaks" that one could have made to AD that would change that behaviour, but I find it highly unlikely that any of that would've been done. I think that something else is happening.
If you don't have failure auditing of account management events enabled, now is a good time to either create a new GPO linked to your "Domain Controllers" OU (the preferred) or to modify your "Default Domain Controllers" GPO (not preferred-- you really shoild leave this GPO "stock) and turn on account management event failure auditing. Dig down into "Computer Configuration", "Windows Settings", "Security Settings", "Local Policies", and "Audit Policy" and enable failure auditing on "Account management".
Run a "gpupdate" on your domain controller comptuers, try your "NET USER" again, and examine the Security Event Log on all your DC's to see which one is recording the failed password change.
I'm keen to figure out what's going on. Like I said, I expect that it's something simple that's being overlooked... We'll see...