A: 

Check your xcdatamodel file for a Deny delete rule. Click on each relationship until you find it. You'll need to change this rule or adjust how you delete managed objects to anticipate the rule's application to the relationship.

Alex Reynolds
I checked, and all my relationships are either Cascade or Nullify.
SooDesuNe
+1  A: 

I'm answering my own question. Please see: Final Update in the initial question.

SooDesuNe
A: 

I had a similar problem where it turned out the problem was in the .xib file. When I switched on the check box for "Deletes Objects on Remove" (under Bindings->Content Set) of the relevant Array Controller, the problem went away.

Don't know if this will help in your case, but I've had a lot of hairs go gray over problems that turned out be hidden away somewhere inside Interface Builder.

pcastine
A: 

Do you happen to implement some of the accessor to the relationship yourself? I once had a code like

-(NSSet*)articles
{
       re-calculates properties....
       return [self primitiveValueForKey:@"articles"];
}

in a subclass of NSManagedObject and had a save error. What happened was that, when this object is deleted from the ManagedObjectContext, the CoreData calls the accessor "articles" to deal with the delete propagation. This re-calculation of articles occurred during the delete propagation, which re-surrected the nullified "articles" in my case.

Yuji