What version are you using ? At first glance, It looks like a bug to me.
Is password history required in your environment ? If not , you can disable it.
I am running 188.8.131.52.0 on Sparc.
I am retaining users past 12 passwords in history, essentially to guarantee they are not recycling them; this is a policy requirement.
To make matter worse, I am having trouble replicating my users claims, which is leading me to believe they are not being truthful :-(