I got that error emailed to me from a customer who just had his new site and was playing around with the new workflow functionality. Needless to say that he was quite disappointed :) So I went to check it out.. First thing I did was to reproduce the problem and funnily enough I also experienced the same error as he did (don't you just love the errors that are reproducible!). Next thing was to create a new custom workflow on that list to see if the error still occurred.. and it did. Next thing to do was to create a new workflow on a new list.. same result.. Then I deactivated (all of) the workflow features.. reactivated them again.. error solved!
In order to really identify and solve the problem I created a new site, based on the same site template and added a workflow to a document library.. started off an approval workflow and guess what.. I experienced the same error. So I created another site, based on another site template and there I noticed it didn't have any workflows activated. So as you might have guessed.. no problems at all when I activated them and created a new workflow.
Now to explain some things about our custom site templates. These are created using the old trick 'Save as template" and then making them available using STSADM. Now the site template is causing the problems had already, during the creation, the workflow features activated. So it seems that during the creation of new a site using that template, the features are not provisioned as they should and therefore are not working properly. That would explain the deactivating and reactivating of the feature to make it work again..
- Create them by copying the STS folder and modify the ONET.XML file and activate the (workflow) features
- Use the "Save as template" thing with all the (workflow) features deactivated and create a custom event handler to activate them during the creation of a new site
Please note that this error occurred on a pre-SP1 environment.