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.
I found this very usefull post
In there they pointed to add the following lines to the web.config
<authorizedType Assembly="mscorlib, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" Namespace="System.Globalization" TypeName="CultureInfo" Authorized="True"/>
That fixed my problem, and I am now happily publishing workflow rules.