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.
Hmm, that doesn't seem to be it. It's a decent size file with a decent number of calculations, but wouldn't be enough to do that. Even when I strip it down to only one sheet, the trace functions aren't working. However, when I open a brand new document in my Excel it works, so there is something happening in that file.
It says "The Trace Dependents command found no formulas that refer to the active cell." when indeed there are plenty. Even if I set up a mock cell where I create it and next to it I refer to that cell, it still gives me the same message.