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.

I'd suspect the users AREN'T meeting the minimum security requirements if they are receiving that message. I wouldn't be surprised if the issue was with the Complexity Requirements being enabled. As per Technet:

Passwords must meet complexity requirements determines whether password complexity is enforced. If this setting is enabled, user passwords meet the following requirements:

The password is at least six characters long.
The password contains characters from at least three of the following:
    English uppercase characters (A - Z)
    English lowercase characters (a - z)
    Base 10 digits (0 - 9)
    Non-alphanumeric (For example: !, $, #, or %)
    Unicode characters
The password does not contain three or more characters from the
    user's account name.

I'd say try disabling the Complexity Requirements to test again.