Asnotb, I think you may be right. I had forgotten about this.
The missing item in that case was page definition for the ProcessAutomation page. In a very interesting way, the files for that page were physically present in the install folder and that page definition itself seemed to be the only thing missing.
What fixed it was simply adding the ProcessAutomation page row into PageDefinition table (I just used one from my 7.1 SP2 test box). I would actually not recommend doing that at once - the error contained reference to what exactly it was looking for and that is what I would be looking for.
Quietleni, I would definitely recommend contacting Technical Support about this. We are interested in trying to find out what makes this happen. What is the Workflow version (including build number) that you are currently on?
After Asnotb's case, I did try upgrading several times in different combinations without running into this issue - 7.1 SP1 -> 7.5; 7.1 SP1 > 7.1 SP2 > 7.5; 7.1 SP2 > 7.5.