This could be either a temporary glitch or any action is dependent on the removed actions.  Please check if any dependency is missing. If everything looks ok, try to save the workflow first and wait 5 to 10 mins then try to publish.

I'm actually having this issue right now. No idea what's causing it. It's isolated to just one site out of all my collections.

I recently exported the workflow, but that shouldn't matter. No other changes have been made. Tasks are now failing because the workflow does not know how to progress through the tree. Anyone have any ideas?

I am having the same exact error on the front end when last week it worked fine but not after patching. 

ULS Error:  Legacy workflow infrastructure Error parsing xoml: <ns0:RootWorkflowActivityWithData x:Class="Microsoft.SharePoint.Workflow.ROOT"...

I have exported the workflow that is failing to start.  Created a New workflow and imported those settings (I tried to republish here and it failed Q.Q).  Deleting an action, trying to publish, and restoring to the baseline export upon failure until I can successfully publish.  I can successfully publish when removing all Request Approvals (I have three of them) I tried to delete them in different order to pin point if it was only one misconfigured or what not.

I hope this helps.  I have other Nintex workflows that are still operating without this issue but they do not have Request Approval action in them.

So if I'm to understand you correctly, you too did some maint such as patches? We did downtime last weekend and this week it seems to have all gone to hell. Trying to see if maybe something changed.

I just attempted editing another workflow on another site that has approvals needed and it DID NOT save. Maybe it was updates.

We applied Microsoft Patches and PSConfig to update SharePoint and that is when we saw the error show above.  I am leaning to Microsoft patch broke something.  Before the patch was applied everything was running successfully.

My test above identified the approval portion was affected some how in this patch for what ever reason. 

Sigh, should have known it wasn't anything we could have done. You are correct though it does only seem to apply to workflows that require an approval. All other workflows are publishing without error or issue. Replicating your steps of deleting all approval requirements worked when trying to publish but obviously those controls are there for a reason. 😛

Any of the big brains around here have any ideas on what might, if anything, need to be changed on the backend to adjust this issue?

I would also ask if you have a similar behavior to confirm if our problems are one in the same. One of the workflows I noticed this problem start happening with is a multi-level approval process. When one user approves it moves onto the next, however, this entire week upon approval from a user to pass it on it just kills/cancels the workflow.

Are you experiencing the same behavior?

My workflow Fails to Start.  I am not sure if its identical or closely related.

That's the identical behavior mine exhibits when attempting to manually start the workflow too. Cool. 

since the actual support here seems to be minimal from anyone "official", here's what seems to be the actual fix to the problem

https://support.microsoft.com/en-us/topic/some-scenarios-of-sharepoint-2010-workflow-are-affected-after-applying-the-july-security-update-for-sharepoint-server-kb5004862-be361cd6-9f54-48c4-b890-2c4b7cf49d13

good luck

I got feedback from Nintex and sharing it here.  Verified it does work.

Microsoft's July 2021 CU has an issue that affects the 2010 workflow engine.
As Nintex also uses this engine, Nintex workflows are affected.
Please see our knowledge Base article which has a solution and a link to the Microsoft blog explaining the issue.
https://community.nintex.com/t5/Technical-Issues/Unable-to-publish-or-run-workflows-after-installing-SharePoint/ta-p/206499
If your issues persist please see the link to Microsoft's blog at the end of the article which contains a workaround for the issue they have caused.

Didn't worked for us. Had to follow the workaround of MS by setting $farm.EnablePreParseSecurityCheckForWorkflow to $false.