Make following things;

1.The particular users are belongs to the db_execute role.

2.The sprocs are given the EXECUTE permission for db_execute role. You can use the below script to see list of procs which do not have EXECUTE permission granted.

SELECT * FROM sysobjects a

LEFT JOIN syspermissions b

ON a.id=b.id

WHERE a.xtype='P'

AND b.id IS NULL