If the SP uses parameters in the WHERE or JOIN clauses, you might investigate the possibility that parameter sniffing caused a bad plan to be cached. There are many excellent articles on parameter sniffing available on SSC, just do a search of articles and blogs.