without the details my friend anthony is asking for, i'd WAG and say to update statistics on the underlying tables the procedure uses.

out of date statistics are associated witht eh symptom you describe: performance of an existing proc slowly degrades.

parameter sniffing could also be an issue...more details might be needed, as anthony suggested.

UPDATE STATISTICS dbo.[Table1] WITH FULLSCAN ;

UPDATE STATISTICS dbo.[Table2] WITH FULLSCAN ;