If there is something not right in the workflow, it will not allow you to publish it. Something as simple as a syntax error. You have to go through and see what error is in your workflow. If necessary, you could even disable most and gradually enable actions until you get to the culprit.
I ended up splitting the workflow into three different workflow, a, b, c and all of them compiled and published fine. So I believe it is the size of the workflow that was causing the issue. Thank you for the comment.
I'll toss this little nugget in the mix as well just in case others come across this issue. My team was deploying workflows to thousands of sites using a PowerShell script (that ultimately uses NWAdmin -o DeployWorkflow) when the script just started erroring with this error no matter what we tried.
In our case the fix ended up being a simple IISRESET on the box we were running the script on and the problem was fixed. Granted kind of a different use case - I suspect others may benefit from knowing that sometimes a good `ol fashioned IISRESET can be all that's needed to fix this though.