Today we were getting this error while trying to start one of those out-of-box Approval workflows: Failed on Start .

After much pain and trial-erroring, we finally got it working thanks to this post we found online:

«...
Changing the identity of the application pool to a user with administrative rights can cause the workflow to “fail to start“. If this sounds like something you've done, try changing it back to network service and try running the workflow again. (worked for me)
...»

Thanks to Raghu Iyer for posting a solution