Users can't change password trough OWA for Exchange 2010

We had a similar issue. It was solved by setting the "Minimum password age" to 0 days.

Setting it to 1 day will prevent users from modifying their password if it is less than a day old, meaning that if it was just reset or changed for testing purposes, you will have to wait 24 hours to change it again.

Leave the complexity requirements as is, and set the minimum password age to 0 and try again.