Generalizing the FFT
While this is not a direct answer, the following discussion on MO (Mathoverflow) relates to finding convolution operations that admit fast FFT-like operations on other algebraic structures.