Interesting concept. Bear in mind SS can go low for quite a while, so syncing might still be a problem.
One of the selling points of the Saleae (bah, I always have to check how that is spelt) is that it can handle massive sample sizes because it uploads them via "bulk USB" protocol (I don't remember it exactly), I think with some sort of data compression. That is, most times the samples are going to be the same, especially at high sample speeds.
Now consider that even using 23A256 chips (256 K bit, that is 32 K bytes) sampling at 20 MHz, you are going to fill up the chip in 1.6 mS, assuming you are sampling 8 channels. Data compression would help a lot (that is, don't record consecutive bytes that are the same) but that requires extra logic, some sort of "smarts" like a CPU can give you.
For that matter, the "SPI sniffer" code I gave in the other thread would run out of RAM really quickly (after all, the Atmega328 only has 2Kb).
For sniffing something highly specific, where you have a nice trigger you can rely on, this could work really well - or even just the Arduino capturing a short burst a 4 MHz.
For more generic debugging, you probably want one of the established logic analyzers.
One other idea is to use a CPLD - something like this:
That is fairly cheap, and you could use that to capture SPI and dump to an SRAM chip.