Eu costumava enfrentar o mesmo problema. Se o aplicativo encadeado estiver usando o mesmo objeto de contexto para todos os encadeamentos, enfrentamos esse tipo de problema. Crie objetos de contexto separados para cada encadeamento. Você pode estar adicionando mais carga na sua RAM, mas dá clareza sobre estados de entidades em Contexto.
List<Task> tasks = new List<Task>();
foreach (var item in list)
{
ObjectContext oContext = new ObjectContext("MyConnection");
Task t = Task.Factory.StartNew(() =>
{
this.Update(item,oContext);
});
tasks.Add(t);
}
Task.WaitAll(tasks.ToArray());
