The error message is:
"An error occurred when the workflow was being created. Try to save the workflow again."
More info:
Running CRM 4.0, with service pack 6 installed. I was able to publish workflows, but the moment I placed a email step on the workflow it did not want to publish, with the above error message.