a referential integrity constraint violation occurred the property values) on the other end

I came across a very similar exception:

"A referential integrity constraint violation occurred: 
The property value(s) of 'ObjectA.PropertyX' on one end of a relationship 
do not match the property value(s) of 'ObjectB.PropertyY' on the other end."
The reason was this: The client side of the web API sent a PUT request with the entire object including the navigation property (in this example ObjectA (more correctly ObjectB.ObjectA) was a navigation property and was fully supplied by the client). This occurs because the client receives the entire object from the server and bounces it as-is back to the server with minor changes.

On the other hand, the ObjectB.PropertyY had just been changed (this was the reason for the PUT request in the first place).

Since ObjectB.PropertyY was a reference to the same object ObjectA (a foreign key), EF tried to reconcile this and failed with the above exception.

The solution was simple:

ObjectB.ObjectA = null;
before the SaveChanges() solved this completely.

I hope this helps someone.