Looking at the error message I think you need to check on 4) above which I mentioned. I pretty much think you might not have updated the right web.config file.
If you know your web application then go to c:\ (or d:) \inetpub\wwwroot\<web application>\ web.confi file. So if you have multiple web applications you may need to change web.config files for all those web applications and if you have multiple WFE then you would need to make changes on each of those servers.
Which resolved our issues,
Well, the deleted history issue may or may not be directly related to this .NET Framework patch. We know from experience that nwadmin utility can delete history for running workflows if you don't specify explicitly which states you purge. On the other hand it's possible (these are only assumptions!) that specific operations on SPWebApplications may terminate or rollback a Nintex Database transaction that was supposed to write the missing history. We suspect that UpdateWorkflowConfigurationSettings could be such breaking operation, but in our case it was the missing piece for the puzzle.
Sorry for the radio silence on this one, in the end we rolled back the security updates and all workflows started firing again. The link Jacob Shihawu shared previously is being touted as the complete fix for this issue.
After speaking with others who have experienced this issue, some people affected running on SharePoint 2010 service pack 1 updated to SP2 which fixed the issue also.
We are planning on adding the updates back in, then following the video step-by-step instructions to see if we can finally put this to bed!