Fortunatelly the issue was cleared out after Operations Team figured out the configuration for the domain account being used by the web service was incorrect. Couple of days looking for something that should not be an issue if the Config wiki page would be followed up step by step (everybody complains when there is no docu, but when it is available there is not being used at all ).
Anyway,if you had the same issue make sure to check the user info has enough privilegies to execute the stored procedure.
Hope this helps somebody else.
Thanks,