Unable to Change User Private Email Address

We recently upgraded to Enterprise 3.1 and since the upgrade I am not able to change the PrivateEmail address on some users (something in the order of 50% of the 60-70 that I have tried to change). It is not all of the users and I haven't been able to figure out what is common between the users that could be causing the issue.

I have tried using the Control Penal | Membership Administration to make the edits. Look up the user, click Edit, go to Email and Contact Info. Then change the Private Email address and click save. That field does not change and there are no errors listed. In fact, I get the normal success message. I can change other profile attributes just fine. But not the Private Email for these specific users.

I have tried making the changes using the REST API to a sample of these same users. Same thing. There is no error reported, but the value does not change.

I have looked in both the Event log and the Exceptions log and there are no entries related to this action in either location.

Before we upgraded to 3.1 from 2.6 this worked 100% of the time. I never had a failure. I am 100% sure that the email address I am trying to set is not already in use anywhere.

Does anyone have a clue what might be causing the problem.