Workflow deployment can be a real pain, here's an error I came across the other day.
Error occurred in deployment step 'Activate Features': Unable to locate the workflow's association data. To restore the association data to the workflow, restart the workflow settings wizard by selecting the workflow node in Solution Explorer and then clicking the ellipsis button (…) on one of the properties in the Properties window that has an ellipsis button.
Even though Visual Studio suggests to reassociate the workflow with task and history lists, I found that the best way to fix this issue is to set Auto Associate to False.