I recently ran into a problem while trying to deploy WSP containing workflow 2013 SPIs. Visual Studio 2012 couldn't delete workflows and workflow associations during deployment process.
After hours of trial and error I noticed that Fiddler was running on the server which is quite common when debugging workflows.
When I closed Fiddler I was able to deploy WSP successfully. I was able to recreate this issue multiple times.
So, close Fiddler when deploying Workflows
It isn't even necessary to close Fiddler, it is enough to stop capturing traffic. This can be achieved by clicking the label "Capturing" in the lower left corner of the status bar: