The EXECUTE permission was denied on the object 'storedProcedureName', database 'databaseName'

Today we deployed an updated version of our web application for my module. In the new module, I created a stored procedure which pull records based on the dates passed. It executed perfectly in my local machine, but when I deployed in our development/testing server, I got the following error:
The EXECUTE permission was denied on the object 'storedProcedureName', database 'databaseName'
We thought that the network\user (active directory user) doesn't have rights to execute the SP, so I contacted the DB team to give rights and it was given. But still I was getting the same error.
Later my onsite coordinator said that we are using service id in our application and that service id should be given rights/access to execute the Stored Procedure.
Service ID would be something like network\svc.yourServiceID
network - your active directory server

Access was given and we were able to execute the stored procedure!!