Correction.
There is a good reason why it was not done before. When I was working on conv nets with Yann LeCun and Patrice Simard in the early 90's some people had tried it but there was no gain. The main reason is that we only had very few channels (like 1 in the input and 5 in the first layer) in the lower layers (where most of the computation took place). When the number of channels becomes large, the advantage of doing the FFT greatly increases because the log(n) overhead can be compensated by the NxN re-use of it through all the NxN channel combinations (N channels in the previous layer times N channels in the next). Also, I don't remember that somebody thought about the advantage brought by this re-use, but I was not involved in this directly so I am not sure.
-- Yoshua