Ah, so there were no no parent documents (that were modified) in this case, and no children either although it did have a number of attachments. We also dumped and recreated the document at least twice with the same no-joy result. The error message was a bit misleading and we didn't come up with anything concrete.
Soo, on a wild guess we started trimming down the attachments and their respective sizes... and ... it worked. Reluctant to say correlation = causation (given the error message of "entry with same key exists") but kinda makes sense on the "operation has timed out" message.