Have you checked the query plan or index fragmentation yet? Those 50000 records might have pushed the fragmentation to the point where it might start running scans instead of seeks.