try to remove the execute right from the affected role, save and grant the execute right again, save and test. Does it help?
I can't believe that fixed it but it did. Thank you for your prompt reply. I'll keep this in mind if I have similar permissions related issues in the future.
Glad to hear it worked...we had something like this a long time ago...