We ran into similar problems, and in the end it was the rights-management of the wcf data service which caused the problems. You should carefully check if all necessary access rules are set for the entity you want to save, which is done in the InitializeService method. NOTE: for saving an entity via wcf data service it is NOT enough to set "EntitySetRights.All" but also set "EntitySetRights.WriteAppend" and "EntitySetRights.WriteMerge" which results in the following line of code:
, EntitySetRights.All | EntitySetRights.WriteAppend | EntitySetRights.WriteMerge);
Also it us very useful to use something like fiddler to check the traffic between client and service.