Workflows are not Terminating

Hello, I have a couple of workflows that I have been using for years. Both workflows have terminating criteria which worked until we upgraded to 13.0. Since we have done the upgrade, the workflows continue processing (sending out emails) until the end of the workflow is reached even if terminating criteria is met first. Has anyone else experienced this? I tried adding additional criteria in case I missed something. I also removed and reentered the terminating criteria but neither one of these worked.