Not sure if this is what is going on with your workbook, but I will tell you where I have seen this occur.
I have seen it where a worksheet has so many calculations, that they are no longer able to trace dependents.
There is an upper limit on how many dependents it can trace (I cannot remember the exact number, but I think it is something like 1 million).
A sign that you may have hit this limit is any time you do anything that results in a recalculation, it takes a few minutes for it to do the calculations (even if the changes are very minor).
That assumes that you are still on Automatic Calculations. If you are on Manual Calculations, you will see the slow performance when you do a Recalc.
If you have hit this trace dependent limit, that may be a sign that you are using the wrong tool for the job. Usually, I see this when people are (often unknowingly) creating a relational database in Excel (having a lot of data related to each other). That is what database programs like Access, SQL, and Oracle are designed for, and handle this sort of thing much better.