Yes, such situations can be frustrating. Have you checked the security permissions on the workflow task list used by the workflow? I ask this as this is a usual suspect. Have you checked the permissions for the user you're delegating to? In other words, have you looked at all that they have access to and cross-referenced that every list in use by your workflow is included in their permissions list? It's onerous, but there's no real way of cheating security.
Whenever I get this message (normally on a newer farm) it always comes down to missing permissions. Good luck!