Well, there's nothing inherent in SQL Server that would result in the system running slower just because of the time passed. You've already hit on what is usually the biggest problem, statistics. Now, you've updated your stats with sp_updatestats, but that's just a sampled update. You could try running a manual statistics update on each of the tables in question:

UPDATE STATISTICS <TableName> WITH FULL SCAN

But, that's only going to help if it's the stats. Your query was running in 2 minutes when everything started. That's not too fast. If it's doing scans against the table and it took 2 minutes when you started and it's still doing scans when your database is big, it could just be that the growth has lead to the slowdown. Have you checked the execution plans for the queries?