Just to get things straight, you have a service that connects to SQL Server, and runs a few procedures. Is this nightly? Hourly? How long does the service take to get through it's routine?
Once the service is done, then users (presumably connecting another way) are complaining that the system is slow? How slow is slow? Next time this happens, take a look at the query plan for this stored procedure you recompile both before you recompile, and after, and see what changes in the execution plan. If there are no changes, you may have a different problem on your hands.