I suddenly ran into the same problem with a fairly basic workbook, where it was taking 20 to 30 seconds for my spreadsheet to update with even the simplest of changes. Often, I would receive a "not responding" message. After spending far too much time searching the web for a solution and troubleshooting my workbook, I found the problem.

I removed the "freeze panes" option on my 6 worksheets. Instant speed and no more of the "not responding" messages. I'm certainly no expert, but it seems to me that this problem could be related to the expanded row and column capability in Excel 2007. If this is the case, quite the gaffe by Microsoft...makes the freeze pane option unusable. I have kept up to date with Office updates, and tried removing them one at a time, but it didn't help. Hope this works for others, and that MS picks up on this soon.