XL 2010 performance issues

Recently I've started to experience some performance slowdowns using XL2010 with XLSX files.

For example, I asked XL to sort a block of cells 3172 rows x 9 columns by 1 of those columns. For the record, I consider this a small sort. XL popped up a warning that this could take a long time -- I've attached a screen-print with the exact message -- and indeed it did: 15 seconds on a machine with a solid-state drive and 3GB of RAM.

For comparison, I converted this XLSX file back to XLS format. When I opened the XLS file in XL2010, performing the same sort was essentially instantaneous; it ran too fast for me to be able to time it.

As mentioned at the top, this sorting slowdown is a recent experience, it only started about a month ago, plus or minus a few weeks. When initially installed, there was no sorting slowdown.

So, what's going on? Why is sorting an XLSX file so slow? How can I fix it?

TIA,
Steve