Cannot Delete Component Error When Trying to Uninstall a Solution

Trying to uninstall a managed solution fails when an option set has a default value and the entity is used in a workflow from a different solution. 

For Example:
1. You create a workflow on Account and add Create Contact step to the workflow.
2. Then you package the workflow with a managed solution and import it to a target system. 
3. You create a custom option set attribute to the contact entity.
4. Then you package this with another solution and install it on to the same target system as the first solution.
5. On the target system open up the workflow editor and click on "Set Properties" button of the Create Contact step. 
5. Save and close both the step editor and workflow editor without changing anything. 
6. Try to uninstall the second solution which installed the option set attribute. 

You will see the following error message:
Cannot Delete Component
Cannot delete Solution because one ore more components require it.

Note: This issue happens even if you don't modify the workflow and properties at all. The issue is that you updated properties of the workflow by clicking save and close.