There are several papers by Markus Püschel on his web site here that discuss Cooley-Tukey-like (so I'm guessing "fast") algorithms for lattice transforms, such as DFTs on triangular and hexagonal 2-D lattices. In the triangular case, he calls the DFT the discrete triangle transform (DTT). Markus has a code called SPIRAL that automatically generates code for transforms, but it appears that this DTT work is not part of SPIRAL, and there is no implementation on his web site that I can find. I'm beginning to think that @J.M. is right and that you might need to roll your own implementation.
One thing that the abstracts note is that for 2-D triangular and hexagonal lattices, the transform is not separable into 1-D components, so you won't be able to reduce the problem to two 1-D transforms.